給定一個(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盅惜。
說明：
- 所有節(jié)點(diǎn)的值都是唯一的中剩。
-
p忌穿、q為不同節(jié)點(diǎn)且均存在于給定的二叉樹中。
來源：劍指Offer第68-II題
相關(guān)企業(yè)：
| 公司 | 出現(xiàn)時(shí)間 |
|---|---|
| 美團(tuán)外賣 | 2020.03 |
| 字節(jié)跳動(dòng) | 2020.03 |
解法：遞歸查找
時(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，說明我們?cè)谶@條尋址線路沒有找到郊愧，我們返回None表示沒找到 - 我們繼續(xù)在左右子樹執(zhí)行相同的邏輯朴译。
- 如果左子樹沒找到，說明在右子樹属铁，我們返回
lowestCommonAncestor(root.right, p , q) - 如果右子樹沒找到眠寿，說明在左子樹，我們返回
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
