Lowest common ancestor of a BST

。題目假設

給定一個 BST，以及兩個點 p, q，找出這兩個點的最低公共祖先

題目假設這兩點一定存在在 BST 裡

。直覺

用遞迴找出

。分析可行性(資結、演算法、虛擬碼)

可以在遞迴時用條件去找出當前的點是不是 p, q 的祖先

。最後解決方案

。反饋：與一開始想的不一樣的地方、需改進的想法

一開始我很注重在 root 跟左右的關係，後來發現題目是要找 p, q 的祖先

而且題目是給一個 BST， BST 的特性是 left.val < root.val < right.val ，

因此只要看看當前的 root 是不是介於 p, q 之間，

如果 root 比 p, q 都大，表示 p, q 都在左子樹，遞迴往 root.left 走

如果 root 比 p, q 都小，表示 p, q 都在右子樹，遞迴往 root.right 走

需改進的地方是：要先想起 BST 的特性

。複雜度

遞迴找到祖先，每次都是往左或往右，因此是 O(log n)

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || p == null || q == null) {
        return root;
    }

    if (root.val > p.val && root.val > q.val) {
        return lowestCommonAncestor(root.left, p, q);
    } else if (root.val < p.val && root.val < q.val) {
        return lowestCommonAncestor(root.right, p, q);
    } else {
        return root;
    }
}