Lowest Common Ancestor

Question

• leetcode: (236)Lowest Common Ancestor of a Binary Tree
• lintcode: (88) Lowest Common Ancestor

Problem Statement

Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.

The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.

Example

For the following binary tree:

  4
 / \
3   7
   / \
  5   6

LCA(3, 5) = 4

LCA(5, 6) = 7

LCA(6, 7) = 7

• reference

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

class Solution:
    # @param {TreeNode} root
    # @param {TreeNode} p
    # @param {TreeNode} q
    # @return {TreeNode}
    def lowestCommonAncestor(self, root, p, q):
        pathP, pathQ = self.findPath(root, p), self.findPath(root, q)
        lenP, lenQ = len(pathP), len(pathQ)
        ans, x = None, 0
        while x < min(lenP, lenQ) and pathP[x] == pathQ[x]:
            ans, x = pathP[x], x + 1
        return ans

    def findPath(self, root, target):
        stack = []
        lastVisit = None
        while stack or root:
            if root:
                stack.append(root)
                root = root.left
            else:
                peek = stack[-1]
                if peek.right and lastVisit != peek.right:
                    root = peek.right
                else:
                    if peek == target:
                        return stack
                    lastVisit = stack.pop()
                    root = None
        return stack