給定一個(gè)二叉樹, 找到該樹中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先。
百度百科中最近公共祖先的定義為：“對(duì)于有根樹 T 的兩個(gè)結(jié)點(diǎn)p、q，最近公共祖先表示為一個(gè)結(jié)點(diǎn) x，滿足x 是 p、q的祖先且 x的深度盡可能大（一個(gè)節(jié)點(diǎn)也可以是它自己的祖先）。”
例如，給定如下二叉樹:
root = [3,5,1,6,2,0,8,null,null,7,4]

二叉樹.png

示例：

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

說(shuō)明：

• 所有節(jié)點(diǎn)的值都是唯一的。
• p、q 為不同節(jié)點(diǎn)且均存在于給定的二叉樹中。

來(lái)源：劍指Offer第68-II題
相關(guān)企業(yè)：

解法：遞歸查找
時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)
思路：由于lowestCommonAncestor(root, p, q)的功能是找出以root為根節(jié)點(diǎn)的兩個(gè)節(jié)點(diǎn)p和q的最近公共祖先。 我們考慮：

• 如果p和q分別是root的左右節(jié)點(diǎn)，那么root就是我們要找的最近公共祖先
• 如果root是None，說(shuō)明我們?cè)谶@條尋址線路沒(méi)有找到，我們返回None表示沒(méi)找到
• 我們繼續(xù)在左右子樹執(zhí)行相同的邏輯。
• 如果左子樹沒(méi)找到，說(shuō)明在右子樹，我們返回lowestCommonAncestor(root.right, p , q)
• 如果右子樹沒(méi)找到，說(shuō)明在左子樹，我們返回lowestCommonAncestor(root.left, p , q)
• 如果左子樹和右子樹分別找到一個(gè)，我們返回root

代碼：

def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if not root or root.val == p.val or root.val == q.val: return root
        l = self.lowestCommonAncestor(root.left,  p , q)
        r = self.lowestCommonAncestor(root.right,  p , q)
        
        return root if l and r else l or r