236_Lowest Common Ancestor of a Binary Tree

236. Lowest Common Ancestor of a Binary Tree

Level: medium

Tag: tree

Question

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).”

Example 1

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

LCA of nodes 5 and 1 is 3
LCA of nodes 5 and 4 is 5

Idea

我们仍然可以用递归来解决，递归寻找两个带查询LCA的节点p和q，当找到后，返回给它们的父亲。如果某个节点的左右子树分别包括这两个节点，那么这个节点必然是所求的解，返回该节点。否则，返回左或者右子树（哪个包含p或者q的就返回哪个）。

Solution: recursive

Time: $O(n)$

Space: $O(1)$

# 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 or root == p or root == q: 
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:
            return root    
        elif left:
            return left
        else: 
            return right

Follow up: what if there is parent pointer?

Idea:

• move p and q upward, record the parent nodes they visited in a set.

• If one node is already visited, then this node is LCA.

Solution:

Time: $O(h)$, where $h$ is the hight of the tree

Space: $O(h)$

def LCA(root, p, q):
    vis = set()
    while p or q:
        if p:
            if p in vis:
                return p
            vis.add(p)
            p = p.parent
        if q:
            if q in vis:
                return q
            vis.add(q)
            q = q.parent
    return None