题目描述:给定一棵二叉树,找到两个节点的最近公共父节点(LCA)。最近公共祖先是两个节点的公共的祖先节点且具有最大深度。【注】假设给出的两个节点都在树中存在。
Solutions
涉及到树的操作一般都联想到递归,而树都是从根节点开始遍历的。
- 如果遍历到当前结点,左子树和右子树的遍历结果都有值,说明当前结点就是要找的最近公共父节点;
- 如果左右子树的遍历结果只有一个有值,说明最近公共父节点在那个有值的子树中。
- 递归出口有很多需要注意。
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param: root: The root of the binary search tree.
@param: A: A TreeNode in a Binary.
@param: B: A TreeNode in a Binary.
@return: Return the least common ancestor(LCA) of the two nodes.
"""
def lowestCommonAncestor(self, root, A, B):
# write your code here
if root is None or root == A or root == B:
return root
left = self.lowestCommonAncestor(root.left, A, B)
right = self.lowestCommonAncestor(root.right, A, B)
if left is not None and right is not None:
return root
if left is not None:
return left
if right is not None:
return right
return None
LeetCode 上有将结果精简到 4 行的操作,很厉害:
def lowestCommonAncestor(self, root, p, q):
if root in (None, p, q): return root
left, right = (self.lowestCommonAncestor(kid, p, q)
for kid in (root.left, root.right))
return root if left and right else left or right