[LeetCode]235. Lowest Common Ancestor of a Binary Search Tree

BST寻找最小祖宗

利用BST的特点，当前节点比两个节点都大，那么祖宗在左子树上，比两个节点都小，那么祖宗在右子树上。

其他情况，祖宗就是当前节点。

难点的题目是普通二叉树的查找：http://www.cnblogs.com/stAr-1/p/8359613.html

/*
    BST寻找最小公共祖先
    根据BST的特点，根据节点的大小值用二分法递归查找就行
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root==null) return null;
        if (root.val>p.val&&root.val>q.val)
            return lowestCommonAncestor(root.left,p,q);
        if (root.val<p.val&&root.val<q.val)
            return lowestCommonAncestor(root.right,p,q);
        return root;
    }