給定一個二叉樹, 找到該樹中兩個指定節(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é)點 5 和節(jié)點 1 的最近公共祖先是節(jié)點 3。
示例 2:
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出: 5
解釋: 節(jié)點 5 和節(jié)點 4 的最近公共祖先是節(jié)點 5瓶盛。因為根據(jù)定義最近公共祖先節(jié)點可以為節(jié)點本身最欠。
- show the code
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if not root or root == p or root == q:
return root
l = self.lowestCommonAncestor(root.left,p,q)
r = self.lowestCommonAncestor(root.right,p,q)
if l and r:
return root
elif l:
return l
elif r:
return r
else:
return
- 此題與上題235. 二叉搜索樹的最近公共祖先(easy)類似，使用遞歸的方法惩猫，分別從左右子樹去尋找p,q的公共節(jié)點即可芝硬，只有這么三種情況：
- 在左、右子樹中分別查找是否包含p或q轧房，如果（兩種情況：左子樹包含p拌阴，右子樹包含q/左子樹包含q，右子樹包含p）锯厢，那么此時的根節(jié)點就是最近公共祖先
- 如果左子樹包含p和q皮官，那么到root->left中查找脯倒，最近公共祖先在左子樹里面
- 如果右子樹包含p和q实辑，那么到root->right中查找捺氢，最近公共祖先在右子樹里面
