050. 最近公共祖先

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

Solutions

References