LeetCode: Lowest Common Ancestor of a Binary Tree – Prepare For Coder Interview

Lowest Common Ancestor of a Binary Tree

Similar Problems:

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

Given the following binary search tree: root = [3,5,1,6,2,0,8,null,null,7,4]

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

Example 1:

Input: root, p = 5, q = 1
Output: 3
Explanation: The LCA of of nodes 5 and 1 is 3.

Example 2:

Input: root, p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself
             according to the LCA definition.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution

## https://code.dennyzhang.com/lowest-common-ancestor-of-a-binary-tree
## Basic Ideas: recursive
##
##   If exists in one subtree, return it.
##   Otherwise, return the root
##
##   Base condition: if root equals one, return root
##
## Complexity: Time O(n), Space O(1)
# 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':
        # empty, or hit one
        if (not root) or root == p or root == q: return root
        r = self.lowestCommonAncestor(root.left, p, q)
        s = self.lowestCommonAncestor(root.right, p, q)
        # Find the nodes from both sub-tree
        if r and s:
            return root
        return r if not s else s

Solution recursive

// https://code.dennyzhang.com/lowest-common-ancestor-of-a-binary-tree
// Basic Ideas: dfs
//
//  Instead of searching both p and q, search one
//
// Complexity: Time O(n), Space O(h)
/**
 * Definition for TreeNode.
 * type TreeNode struct {
 *     Val int
 *     Left *ListNode
 *     Right *ListNode
 * }
 */
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil { return nil }
    // found either one
    if root == p || root == q {
        return root
    }
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)
    if left != nil && right != nil {
        return root
    }
    if left != nil {
        return left
    } else {
        return right
    }
}

Solution: Caculate the visit path

// https://code.dennyzhang.com/lowest-common-ancestor-of-a-binary-tree
// Basic Ideas: dfs
//
// Complexity: Time O(n), Space O(h)
/**
 * Definition for TreeNode.
 * type TreeNode struct {
 *     Val int
 *     Left *ListNode
 *     Right *ListNode
 * }
 */
func dfs(root *TreeNode, target *TreeNode, path *[]*TreeNode) bool {
    if root == nil {
        return false
    }
    // update path
    *path = append(*path, root)
    if root == target {
        return true
    }
    if dfs(root.Left, target, path) {
        return true
    }
    if dfs(root.Right, target, path) {
        return true
    }
    *path = (*path)[0:len(*path)-1]
    return false
}

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    l1 := []*TreeNode{}
    dfs(root, p, &l1)

    l2 := []*TreeNode{}
    dfs(root, q, &l2)

    i := 0
    for ; i<len(l1) && i<len(l2); i++ {
        if l1[i] != l2[i] {
            break
        }
    }
    return l1[i-1]
}

## https://code.dennyzhang.com/lowest-common-ancestor-of-a-binary-tree
## Basic Ideas: recursive
##
## Notice:
##   Here we assume p, q will exists in the tree
##
## Complexity: ?
# 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 is None 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
        return left if left else right

Post Views: 4