AcWing 88. 树中两个结点的最低公共祖先
原题链接
中等
作者:
zc2077
,
2020-07-13 08:33:54
,
所有人可见
,
阅读 512
递归
- 对当前节点r的左子树、右子树递归,若左右都查找到了p、q节点,那么r便是最低公共祖先;
- 若只有一边查到了p、q节点,说明,p、q节点中的其中一个是最低公共祖先,直接返回该节点;
- 边界:空节点,返回空指针;
- 边界:若当前节点属于p、q中的某一个,直接返回该节点;
# 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:
return None
if root in [p, q]:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
if left:
return left
if right:
return right