Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

    _______3______
   /              \
___5__          ___1__
   /      \        /      \
   6      _2       0       8
     /  \
     7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Solution

我们可以用深度优先搜索，从叶子节点向上，标记子树中出现目标节点的情况。如果子树中有目标节点，标记为那个目标节点，如果没有，标记为null。显然，如果左子树、右子树都有标记，说明就已经找到最小公共祖先了。如果在根节点为p的左右子树中找p、q的公共祖先，则必定是p本身。
换个角度，可以这么想：如果一个节点左子树有两个目标节点中的一个，右子树没有，那这个节点肯定不是最小公共祖先。如果一个节点右子树有两个目标节点中的一个，左子树没有，那这个节点肯定也不是最小公共祖先。只有一个节点正好左子树有，右子树也有的时候，才是最小公共祖先。

(LCA-of-a-Binary-Tree.py) download

# 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 root == None or root == p or root == q:
            return root
        leftTree = self.lowestCommonAncestor(root.left,p,q)
        rightTree = self.lowestCommonAncestor(root.right,p,q)

        # 这个root刚好左右子树各有一个目标节点
        if leftTree != None and rightTree != None:
            return root
        # 只有左子树有目标
        if leftTree != None:
            return leftTree
        else:
            # 只有右子树有目标
            return rightTree

卖萌的弱渣

I am stupid, I am hungry.

Lowest Common Ancestor of a Binary Tree

Solution