LeetCode 235: Lowest Common Ancestor of a Binary Search Tree

/**
 * 235. Lowest Common Ancestor of a Binary Search Tree
 * 1. Time:O(n)  Space:O(n)
 * 2. Time:O(n)  Space:O(1)
 */

// 1. Time:O(n)  Space:O(n)
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int val = root.val;
        int val1 = p.val;
        int val2 = q.val;
        if(val1<val && val2<val)
            return lowestCommonAncestor(root.left,p,q);
        else if(val1>val && val2>val)
            return lowestCommonAncestor(root.right,p,q);
        else
            return root;
    }
}

// 2. Time:O(n)  Space:O(1)
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int pVal = p.val;
        int qVal = q.val;
        TreeNode cur = root;
        while(cur!=null){
            int rootVal = cur.val;
            if(pVal<rootVal && qVal<rootVal)
                cur = cur.left;
            else if(pVal>rootVal && qVal>rootVal)
                cur = cur.right;
            else
                return cur;
        }
        return null;
    }
}

LeetCode 235: Lowest Common Ancestor of a Binary Search Tree

原文：https://www.cnblogs.com/AAAmsl/p/12842077.html