您好,登录后才能下订单哦!
这篇文章给大家介绍如何解析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:=0
if 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 []*TreeNode
if 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二叉树的最近公共祖先就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。