Lowest Common Ancestor of a Binary Search Tree

thoughts

• BST 性質：左子樹 < root < 右子樹
• 若 p 和 q 都比 root 小 → 在左子樹
• 若 p 和 q 都比 root 大 → 在右子樹
• 否則 root 就是 LCA

kotlin

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    fun lowestCommonAncestor(root: TreeNode?, p: TreeNode?, q: TreeNode?): TreeNode? {
        var node = root
        while (node != null) {
            if (p!!.`val` < node.`val` && q!!.`val` < node.`val`) {
                node = node.left
            } else if (p.`val` > node.`val` && q.`val` > node.`val`) {
                node = node.right
            } else {
                return node
            }
        }
        return null
    }
}

follow up

• 如果是 普通二元樹（不是 BST）怎麼辦？（需 DFS 遞迴）
• 如果樹很大，可以考慮 儲存父節點，再走訪到 root 找交集。
• 如果輸入是 多個節點的 LCA，怎麼改？