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

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

 思路：公共祖先相比左节点大，右节点小，所以第一个数据范围在这两个间的一定是最近公共祖先。

/**
 * 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) {
        return getRes(root,p,q);
    }

    private TreeNode getRes(TreeNode root, TreeNode p, TreeNode q){

        if(root.val > q.val&&root.val > p.val){
            return getRes(root.left,p,q);
        }

        if(root.val < p.val&&root.val < q.val){
            return getRes(root.right,p,q);
        }

        return root;
    }
}