Leetcode-235: 二叉搜索树的最近公共祖先

题目描述：
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

思路：
利用二叉搜索树的性质，如果p,q 的值在root的两侧，则直接返回root，如果p,q值都小于root值，那么在root.left中查找。如果p,q值都大于root值，那么在root.right中查找。

/**
 * 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) {
        if(root==null)
            return root;
        if(root==p || root==q)
            return root;
        if((root.val-p.val)* (root.val-q.val)<0)
            return root;
        else if(root.val > p.val && root.val >q.val)
            return lowestCommonAncestor(root.left,p,q);
        else if(root.val < p.val && root.val < q.val)
            return lowestCommonAncestor(root.right,p,q);
        return null;
    }
}