溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
python二叉樹中的最近公共祖先是什么，針對這個問題，這篇文章詳細介紹了相對應的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。
給定一個二叉搜索樹, 找到該樹中兩個指定節點的最近公共祖先。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）。”
例如，給定如下二叉搜索樹: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 輸出: 6 解釋: 節點 和節點 的最近公共祖先是
示例 2:
輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 輸出: 2 解釋: 節點 和節點 的最近公共祖先是 , 因為根據定義最近公共祖先節點可以為節點本身。
說明:
所有節點的值都是唯一的。
p、q 為不同節點且均存在于給定的二叉搜索樹中。
解題思路：
1，利用二叉搜索樹的性質：
A，去過p，q最大值小于根節點則，祖先在左子樹
B，最小值大于根節點，祖先在右子樹
C，祖先是根節點
2，注意p，q的大小未定
/*** Definition for TreeNode.* type TreeNode struct {* Val int* Left *ListNode* Right *ListNode* }*/func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {if root==nil{return root}if p.Val<q.Val{return lca(root,p,q)}return lca(root,q,p)}func lca(root,p,q *TreeNode)*TreeNode{if root.Val<p.Val{return lca(root.Right,p,q)}if root.Val>q.Val{return lca(root.Left,p,q)}return root}
給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先。
百度百科中最近公共祖先的定義為：“對于有根樹 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 解釋: 節點 和節點 的最近公共祖先是節點
示例 2:
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 輸出: 5 解釋: 節點 和節點 的最近公共祖先是節點 因為根據定義最近公共祖先節點可以為節點本身。
說明:
所有節點的值都是唯一的。
p、q 為不同節點且均存在于給定的二叉樹中。
解題思路：
1，如果左子樹包含p，右子樹包含q，說明，根即為解
2，如果p，q均在左子樹，則遞歸左子樹
3，若p，q均在右子樹，則，遞歸右子樹
/*** Definition for TreeNode.* type TreeNode struct {* Val int* Left *ListNode* Right *ListNode* }*/func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {if root==nil || p==nil ||q==nil {return nil}if root.Val==p.Val && root.Val==q.Val{return root}cur:=rootfor contain(cur,p)&& contain(cur,q){if contain(cur.Left,p)&& contain(cur.Left,q){cur=cur.Left}else if contain(cur.Right,p)&& contain(cur.Right,q){cur=cur.Right}else{return cur}}return nil}func contain(root, p *TreeNode) bool{if root==nil || p==nil {return false}return root.Val==p.Val || contain(root.Left,p) ||contain(root.Right,p)}
關于python二叉樹中的最近公共祖先是什么問題的解答就分享到這里了，希望以上內容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關注億速云行業資訊頻道了解更多相關知識。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
