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

因为是二叉搜索树 所以左边小 右边大
递归

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int pval = p.val;
        int qval = q.val;
        if(root.val>pval&&root.val>qval) return lowestCommonAncestor(root.left, p, q);
        if(root.val<pval&&root.val<qval) return lowestCommonAncestor(root.right, p, q);
        return root;
    }
}

递推

class Solution {
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(root!=null) {
            int pval = p.val;
            int qval = q.val;
            int rootval = root.val;
            if(rootval > pval&&rootval>qval) {
                root = root.left;
            }
            else if(rootval < pval&&rootval<qval) {
                root = root.right;
            }
            else return root;
        }
        return null;
    }
}