Skip to content

236.lowest-common-ancestor-of-a-binary-tree.md

Latest commit

 

History

History
199 lines (169 loc) · 6.07 KB

236.lowest-common-ancestor-of-a-binary-tree.md

File metadata and controls

199 lines (169 loc) · 6.07 KB

236. Lowest Common Ancestor of a Binary Tree

Clarification Questions

  • Does it guarantee that p and q are in the tree?
  • Is every value unique in the tree?
  • Is p and q the same node?

Test Cases

Normal Cases

Input: p = 2, q = 3
       1
     /   \
    2     3
Output: 1

Input: p = 2, q = 1
       1
     /   \
    2     3
Output: 1

Edge / Corner Cases

  • p and q are the same node.
Input: p = 1, q = 1
       1
     /   \
    2     3
Output: 1

Input: p = 2, q = 2
       1
     /   \
    2     3
Output: 2

Maintain Parent Nodes

We update the parent node of each node in the tree until we find both p and q. Then we traverse to find the path from p to the root and q to the root. The first common node in the path is the LCA.

fun lowestCommonAncestor(root: TreeNode, p: TreeNode?, q: TreeNode?): TreeNode? {
    val stack = Stack<TreeNode>()
    val parentMap = mutableMapOf<TreeNode, TreeNode?>()

    stack.push(root)
    parentMap.put(root, null)
    while (!stack.isEmpty() && (!parentMap.contains(p) || !parentMap.contains(q))) {
        val n = stack.pop()

        if (n.left != null) {
            parentMap.put(n.left, n)
            stack.push(n.left)
        }
        if (n.right != null) {
            parentMap.put(n.right, n)
            stack.push(n.right)
        }
    }

    val ancestorSet = mutableSetOf<TreeNode>()
    var n: TreeNode? = p
    while (n != null) {
        ancestorSet.add(n)
        n = parentMap[n]
    }

    n = q
    while (n != null) {
        if (ancestorSet.contains(n)) return n
        n = parentMap[n]
    }
    return root
}
  • Time Complexity: O(n).
  • Space Complexity: O(n).

Recursive

給定一個二叉樹 root 和 p 和 q 兩個節點，我們怎麼求這兩個節點的最近公共祖先？我們先來分類討論一下：

  • 當前節點是 null: 我們直接返回 null 即可。
  • 當前節點是 p 或 q: 我們還需要繼續往下找嗎？不需要的，舉例來說我們找到 p = 5，假設 q 在 5 子樹的任何地方，答案都會是 5。所以這情況我們直接返回當前節點。
        1
     /     \
    5(p)     3
   / \     / \
  6   2   0   8
     / \
    7   4
  • 其他: 是否找到 p 或 q
    • 左、右子樹找到了: 返回當前節點
           1(lca)
    /     \
   5(p)    3
  / \     / \
 6   2   0   8(q)
 ...
    • 只有左子樹找到了: 表示 p 跟 q 都在左子樹，我們返回遞迴左子樹的結果即可。
            1
    /       \
   5(p,lca)  3
  / \        ...
 6   2(q) 
 ...
    • 只有右子樹找到了: 同上
    • 都沒找到: 返回 null 即可。

There are two cases:

  1. p and q are in the same subtree.
        root
        /
      p
     /
   ...
   /  \
       q
  1. p and q are in different subtrees.
     root
     /
   ...
   /  \
  p    q

Suppose we start the recursion to traverse from the root node, to search for p and q both in the left and right subtrees. And we terminate the recursion when the node is null or we find p or q.

        root
     /        \
   LCA(L)    LCA(R)
  • If LCA(L) and LCA(R) are not null, that we find p and q in the different subtrees, means p and q are in different subtrees, then the current root is the LCA.
  • If LCA(L) is not null but LCA(R) is null, that means p and q are in the left subtree, then the LCA is LCA(L), and vice versa.

Idea!! So the idea is to find p and q in the left and right subtrees. If we find both, then the current node is the LCA. If we find one of them, then we return it. If we find none of them, then we return null. You can think as that we use the function to find p or q, not finding the LCA.

fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
    // Return null if we reach the leaf node and we don't find p and q.
    if (root == null || p == null || q == null) return null

    // If we find one of the nodes, just return it.
    if (root == p || root == q) return root

    // We search p and q in the left and right subtree.
    val left = lowestCommonAncestor(root?.left, p, q)
    val right = lowestCommonAncestor(root?.right, p, q)

    // If we find both from left and right subtree, that indicates 
    // that p and q are in different subtree, then 
    // the current node is the LCA.
    if (left != null && right != null) return root

    // If one subtree returns a node (p or q) and 
    // the other subtree returns null, indicates that
    // p and q is in the same subtree, then return the node directly
    return left ?: right
}
  • Time Complexity: O(n).
  • Space Complexity: O(h).

Here is nice explanation: https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/solution/236-er-cha-shu-de-zui-jin-gong-gong-zu-xian-jian-j/

两个节点 p,q 分为两种情况：

  • p 和 q 在相同子树中

  • p 和 q 在不同子树中 从根节点遍历，递归向左右子树查询节点信息 递归终止条件：如果当前节点为空或等于 p 或 q，则返回当前节点

  • 递归遍历左右子树，如果左右子树查到节点都不为空，则表明 p 和 q 分别在左右子树中，因此，当前节点即为最近公共祖先；

  • 如果左右子树其中一个不为空，则返回非空节点。

Or another nice explanation:

既在左子树找p和q，又在右子树找p和q。 只要找到p或q的其中一个就可以返回，如果left和right都不为空，说明左右子树各找到p和q当中的一个，那么p和q在root的两侧。 如果left不为空，说明p,q在左子树。 如果right不为空，说明p,q在右子树。 left和right都为空，说明找不到。

当p为q的祖先节点时，搜索一侧子树只能返回p，这时候搜另一边是搜不到q的，但节点又一定在树中，所以一定是p是q的祖先的情况，直接返回p即为答案。

      /
     p
    / \
   q   ...