题目描述

二叉搜索树的最近公共祖先

样例

blablabla

算法1:Iteration

时间复杂度O(logN)

参考文献

Java 代码

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int pVal = p.val, qVal = q.val;
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val > Math.max(pVal, qVal)) {
                cur = cur.left;
            }
            else if (cur.val < Math.min(pVal, qVal)) {
                cur = cur.right;
            }
            else break;
        }

        return cur;
    }
}

算法2: Recursion

时间复杂度

O(logn)

参考文献

Java 代码

/*
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
/

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int i = p.val, j = q.val;
        if (root.val > Math.max(i, j)) {
            return lowestCommonAncestor(root.left, p, q);
        }
        if (root.val < Math.min(i, j)) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }
}