Lowest Common Ancestor of a Binary Tree

Problem Id: 236 Difficulty: Medium Tag: Tree


Intuition

Using DFS, and in the dfs function, return 2 values p_visited and q_visited. When the first time p_visited equals to q_visited, set the result and return the result.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        return self._helper(root, p, q)[-1]

    def _helper(self, node, p, q):
        if node is None:
            return False, False, None
        lp, lq, l = self._helper(node.left, p, q)
        rp, rq, r = self._helper(node.right, p, q)
        if l or r:
            return True, True, l or r
        p_visited = lp or rp or (node == p)
        q_visited = lq or rq or (node == q)
        if p_visited and q_visited:
            return True, True, node
        return p_visited, q_visited, None