235. Lowest Common Ancestor of a Binary Search Tree - Medium

前往題目

想法

• 這題之前寫過，這次嘗試寫出來但只對了一半，有冗餘條件

思路

這題重點就只有條件，看出條件就解出來了

因為BST的特性所以:

• 當p和q的值大於root，就要往右邊找，因為一定在右邊；反之，往左邊找
• 當p和q不是都大於或小於root的值就代表找到那個LCA了

Code

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;

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

        return root;
    }
}