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

这道题要充分利用二叉搜索树的性质，即比某一节点大的数全在其右侧，比其小的数全在其左侧。

思路：

知道了二叉搜索树的性质后，根据其性质可知，如果p和q在节点temp的两侧的话，也就是当（p.val - temp.val）*(q.val - temp.val)<=0时（包含“=”号，因为“一个节点也可以是它自己的祖先”），则当前节点temp就是它们的最近公共祖先。否则说明p和q都在temp的某一侧，如果在左侧的话，那么就让temp = temp.left，循环递进比较即可。

解法一：递归法

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if((root.val - p.val) * (root.val - q.val) <=0){
            return root;
        }else if(root.val - p.val > 0){
            root = lowestCommonAncestor(root.left,p,q);
        }else{
            root = lowestCommonAncestor(root.right,p,q);
        }
        return root;
    }

解法二：迭代法

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