您好,登錄后才能下訂單哦!
這篇文章給大家介紹如何解析python二叉樹的最近公共祖先,內(nèi)容非常詳細(xì),感興趣的小伙伴們可以參考借鑒,希望對大家能有所幫助。
給定一個二叉樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。
百度百科中最近公共祖先的定義為:“對于有根樹 T 的兩個結(jié)點 p、q,最近公共祖先表示為一個結(jié)點 x,滿足 x 是 p、q 的祖先且 x 的深度盡可能大(一個節(jié)點也可以是它自己的祖先)。”
例如,給定如下二叉樹: 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
解釋: 節(jié)點 5 和節(jié)點 1 的最近公共祖先是節(jié)點 3。
示例 2:
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出: 5
解釋: 節(jié)點 5 和節(jié)點 4 的最近公共祖先是節(jié)點 5。因為根據(jù)定義最近公共祖先節(jié)點可以為節(jié)點本身。
說明:
所有節(jié)點的值都是唯一的。
p、q 為不同節(jié)點且均存在于給定的二叉樹中。
解法一:
1,如果兩個節(jié)點分別在左右子樹,返回當(dāng)前節(jié)點
2,如果都在左子樹,遞歸左子樹
3,如果都在右子樹,遞歸右子樹
代碼實現(xiàn)
/** * 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,找出從根節(jié)點到兩個點的路徑
2,去掉重合部分
代碼實現(xiàn)
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
}
關(guān)于如何解析python二叉樹的最近公共祖先就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,可以學(xué)到更多知識。如果覺得文章不錯,可以把它分享出去讓更多的人看到。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。