尋找共同祖先

輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 輸出: 3 解釋: 節點 5 和節點 1 的最近公共祖先是節點 3。

首先是需要構造樹

class BinTNode:def __init__(self,data=None,left =None,right =None):self.data =dataself.left =leftself.right =rightdef buildTree1(arr,pointer,N):if pointer <=N:if arr[pointer] == -1:curNode = Noneelse:curNode = BinTNode(arr[pointer])if 2*pointer+1<=N:curNode.left = buildTree(arr,2*pointer+1,N)if 2*pointer+2<=N:curNode.right = buildTree(arr,2*pointer+2,N)return curNode# 如下是簡化的版本，我們一般在循環里盡量少用判斷語句 def buildTree(arr,pointer,N):# 遞歸出口，當越界時就沒有必要創建節點了直接return，開始回退# 當值為-1時，也沒有必要創建結點if pointer > N or arr[pointer] == -1:return NonecurNode = BinTNode(arr[pointer])curNode.left = buildTree(arr,2*pointer+1,N)curNode.right = buildTree(arr,2*pointer+2,N)return curNode

尋找兩個孩子的共同祖先：我們定義問題為找共同祖先，當一顆子樹只含有child1時，

那么這顆子樹的祖先就是child1，一顆子樹只含有child2時，那么這顆子樹的祖先就是child2，

當一顆子樹同時含有child1和child2時，那么他的祖先就是child1和child2的共同祖先，然后把問題縮小到一顆子樹

def findAncestor(root,child1,child2):if not root:return -1# 把原問題分成三個部分，左子樹，當前結點，右子樹if root.data == child1 or root.data ==child2:# 不管下面還有沒有要找的child,整顆樹的祖先都是rootreturn root.data# 如果root不是任何一個的祖先，就需要處理下面的2顆子樹left_ancestor = findAncestor(root.left,child1,child2)right_ancestor = findAncestor(root.right,child1,child2)# 然后基于兩顆子樹得到的結果處理,分為六種情況:# 左0右0，-1， left_ancestor + right_ancestor + 1# 左1右1，root.data, root.data# 左1右0，left_ancestor left_ancestor + right_ancestor + 1# 左0右1，right_ancestor left_ancestor + right_ancestor + 1# 左2右0，left_ancestor left_ancestor + right_ancestor + 1# 左0右2，right_ancestor left_ancestor + right_ancestor + 1if left_ancestor !=-1 and right_ancestor !=-1:return root.data# 這個簡化處理非常巧妙，一般寫循環盡量少用判斷，可以巧妙利用返回值-1構造通用結果# 看這個處理直接把其他的5種結果都處理成left_ancestor + right_ancestor + 1# 利用返回的結果為-1，+1之后可以消除可能出現的那個結果return left_ancestor + right_ancestor + 1# 這種方案存在問題，當一顆子樹只含有child1時， # 那么這顆子樹的祖先就是child1，一顆子樹只含有child2時，那么這顆子樹的祖先就是child2， # 但是最終方案是求共同祖先，如果輸入一個孩子不存在，那返回結果不久變成了兩外一個孩子def findAncestor2(root,child1,child2):# 把原問題分成三個部分，左子樹，當前結點，右子樹if (not root) or root.data == child1 or root.data ==child2:# 不管下面還有沒有要找的child,整顆樹的祖先都是root return root# 如果root不是任何一個的祖先，就需要處理下面的2顆子樹 # left_ancestor =None # right_ancestor =Noneleft_ancestor = findAncestor2(root.left,child1,child2)right_ancestor = findAncestor2(root.right,child1,child2)# 然后基于兩顆子樹得到的結果處理,分為六種情況:# 左0右0，none， [left_ancestor , right_ancestor]# 左1右1，root, root# 左1右0，left_ancestor [left_ancestor , right_ancestor]# 左0右1，right_ancestor [left_ancestor , right_ancestor ]# 左2右0，left_ancestor [left_ancestor , right_ancestor]# 左0右2，right_ancestor [left_ancestor , right_ancestor]if left_ancestor and right_ancestor:return root# 這個簡化處理非常巧妙，一般寫循環盡量少用判斷，可以巧妙利用返回值-1構造通用結果# 看這個處理直接把其他的5種結果都處理成left_ancestor + right_ancestor + 1# 利用返回的結果為-1，+1之后可以消除可能出現的那個結果return (left_ancestor,right_ancestor)[not left_ancestor]# leetcode 236 # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution:def lowestCommonAncestor(self, root, p, q):""":type root: TreeNode:type p: TreeNode:type q: TreeNode:rtype: TreeNode"""if (not root) or root.data == p or root.data ==q: return rootleft_ancestor = self.lowestCommonAncestor(root.left,p,q)right_ancestor = self.lowestCommonAncestor(root.right,p,q)if left_ancestor and right_ancestor:return root# 比較三種情況的處理return left_ancestor if left_ancestor else right_ancestor

運行結果

arr =[1,2,3,4,5,6,7,-1,-1,8,9,-1,-1,10,11] root = buildTree(arr,0,len(arr)-1) print(findAncestor(root,9,5)) print(findAncestor2(root,9,5).data) print(Solution().lowestCommonAncestor(root,9,5).data)runfile('D:/share/test/buildTree.py', wdir='D:/share/test') 5 5 5

這3種方案存在問題，當一顆子樹只含有child1時，

那么這顆子樹的祖先就是child1，一顆子樹只含有child2時，那么這顆子樹的祖先就是child2，

但是最終方案是求共同祖先，如果輸入一個孩子不存在，那返回結果不久變成了兩外一個孩子

總結

以上是生活随笔為你收集整理的树形结构：寻找共同祖先的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。