BST:最近公共祖先

    给定一棵二叉搜索树和其中的两个节点,要求寻找其最近的公共祖先(祖先可以是其本身)

    思路:由于是二叉搜索树,每个节点的所有左节点都小于该节点,所有右节点都大于该节点,因此,两个节点“分叉”的地方就是它们的最近公共祖先

    方法一:

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

    方法二:对于“两个节点分叉”这个条件,可以反过来:不分叉的时候往下移动,否则返回当前节点。判断方法也可以改进

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while ((root.val - p.val) * (root.val - q.val) > 0)    //同时大于当前节点或同时小于当前节点
        root = p.val < root.val ? root.left : root.right;
    return root;
}

    方法三:使用递归的方法,如果分叉,返回当前节点,否则向下递归。只需要一行代码!

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


;