如何解析python二叉树的最近公共祖先
这篇文章给大家介绍如何解析python二叉树的最近公共祖先，内容非常详细，感兴趣的小伙伴们可以参考借鉴，希望对大家能有所帮助。
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。
解法一：
1，如果两个节点分别在左右子树，返回当前节点
2，如果都在左子树，递归左子树
3，如果都在右子树，递归右子树
代码实现
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func lowestCommonAncestor(root *TreeNode, p *TreeNode, q *TreeNode) *TreeNode { if root!=nil && contain(root.Left,p)&& contain(root.Left,q){ return lowestCommonAncestor(root.Left,p,q) } if root!=nil && contain(root.Right,p)&& contain(root.Right,q){ return lowestCommonAncestor(root.Right,p,q) } return root}func contain(root *TreeNode, p *TreeNode)bool{ if root==nil{ return false } if root.Val==p.Val{ return true } return contain(root.Left,p)||contain(root.Right,p)}
解法二：
1，找出从根节点到两个点的路径
2，去掉重合部分
代码实现
func lowestCommonAncestor(root *TreeNode, p *TreeNode, q *TreeNode) *TreeNode{var l,r []*TreeNode_,l=findPath(root,p)_,r=findPath(root,q)l=append([]*TreeNode{root},l...)r=append([]*TreeNode{root},r...)// for i:=0;i<len(l);i++{// fmt.Println("l->",l[i].Val)// }// for j:=0;j<len(r);j++{// fmt.Println("r->",r[j].Val)// }i:=0if len(l)==0 ||len(r)==0{return root}for i<len(l)&&i<len(r)&&l[i].Val==r[i].Val{i++}return l[i-1]}func findPath(root *TreeNode, p *TreeNode)(bool,[]*TreeNode){var path []*TreeNodeif root==nil{return false,path}if root.Val==p.Val{return true,path}if ok,path:=findPath(root.Left,p);ok{path=append([]*TreeNode{root.Left},path...)//fmt.Println(root.Left.Val,"len",len(path))return true,path}if ok,path:=findPath(root.Right,p);ok{path=append([]*TreeNode{root.Right},path...)//fmt.Println(root.Right.Val,"len",len(path))return true,path}return false,path}
关于如何解析python二叉树的最近公共祖先就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。