题目描述:给定一棵二叉树,找到两个节点的最近公共父节点(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

References

  1. 050. 最近公共祖先
  2. 4 lines C++/Java/Python/Ruby
  3. 235 Leetcode