python二叉樹中的最近公共祖先是什么

python二叉樹中的最近公共祖先是什么，針對這個問題，這篇文章詳細介紹了相對應(yīng)的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。

給定一個二叉搜索樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。

百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結(jié)點 p、q，最近公共祖先表示為一個結(jié)點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）?！?/p>

例如，給定如下二叉搜索樹:  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 
解釋: 節(jié)點 和節(jié)點 的最近公共祖先是

示例 2:

輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
輸出: 2
解釋: 節(jié)點  和節(jié)點  的最近公共祖先是 , 因為根據(jù)定義最近公共祖先節(jié)點可以為節(jié)點本身。

說明:

• 所有節(jié)點的值都是唯一的。

• p、q 為不同節(jié)點且均存在于給定的二叉搜索樹中。

解題思路：

1，利用二叉搜索樹的性質(zhì)：

A，去過p，q最大值小于根節(jié)點則，祖先在左子樹

B，最小值大于根節(jié)點，祖先在右子樹

C，祖先是根節(jié)點

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}

給定一個二叉樹, 找到該樹中兩個指定節(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é)點 和節(jié)點 的最近公共祖先是節(jié)點

示例 2:

輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出: 5
解釋: 節(jié)點 和節(jié)點 的最近公共祖先是節(jié)點 因為根據(jù)定義最近公共祖先節(jié)點可以為節(jié)點本身。

說明:

• 所有節(jié)點的值都是唯一的。

• p、q 為不同節(jié)點且均存在于給定的二叉樹中。

解題思路：

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:=root     for 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)}

關(guān)于python二叉樹中的最近公共祖先是什么問題的解答就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識。