Lowest Common Ancestor of a Binary Tree

LC 236 題意

• 給定一棵二元樹與兩個節點 p 和 q，找出它們的最低共同祖先（LCA）。
• LCA 定義：同時是 p、q 祖先的節點中，距離最遠的節點。
• Example
  Input: root = [3,5,1,6,2,0,8,null,null,7,4], p=5, q=1
  Output: 3

thoughts

• DFS + 回傳節點法
  • 若當前節點是 p 或 q，回傳自己。
  • 遞迴搜尋左右子樹：
    • 若左右皆非空 → 當前節點為 LCA。
    • 若僅一邊非空 → 回傳該子樹結果。

Kotlin 解法

class Solution {
    fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
        if (root == null || root == p || root == q) return root
        val left = lowestCommonAncestor(root.left, p, q)
        val right = lowestCommonAncestor(root.right, p, q)
        return when {
            left != null && right != null -> root
            left != null -> left
            else -> right
        }
    }
}

Follow-up

• 若節點含有 parent pointer？
  • → 可向上追蹤 + HashSet 標記祖先節點。
• 若是 BST，如何更快？
  • → 若 p、q 值都小於 root，往左；若都大於 root，往右。
• 若是多叉樹（N-ary tree）？
  • → 遞迴改為遍歷所有 children，收集非空結果。