Lowest Common Ancestor

The lowest common ancestor (LCA) (also called least common ancestor) of two nodes u and v in a tree or directed acyclic graph (DAG) T is the lowest (i.e. deepest) node that has both v and w as descendants.

1. u, v are lca‘s descendant
   (each node can be a descendant of itself)
2. path_from_root_to_lca := [root, …, lca]
   path_from_root_to_u := [root, …, u]
   path_from_root_to_v := [root, …, v]

   path_from_root_to_lca ⊆ path_from_root_to_u and path_from_root_to_lca ⊆ path_from_root_to_v
   (path_from_root_to_u – path_from_root_to_lca) ∩ (path_from_root_to_v – path_from_root_to_lca) = ∅

LCA in Binary Liftin

Binary Lifting

是一種 Bottom-UP 的 dynamic programming

假設要找node的第k個祖先
把k拆成 k == k₀ + k₁ + k₂ + … + k_n, log₂(k_i) ∈ {0} ∪ ℕ, k_i > k_{i + 1}
要花 O(n) 的 time/space complexity 建立 table
(dp[i][node] := node 的第 2 ** i 個祖先)
但搜尋node的第k個祖先只需要 O(log(k)) 的 time complexity

• Leetcode # 1483. ⭐️ Kth Ancestor of a Tree Node

相關例題

• Leetcode # 235. Lowest Common Ancestor of a Binary Search Tree
• Leetcode # 1483. ⭐️ Kth Ancestor of a Tree Node
• Leetcode # 1644. Lowest Common Ancestor of a Binary Tree II
• Leetcode # 2846. Minimum Edge Weight Equilibrium Queries in a Tree

Last Updated on 2023/09/12 by A1go