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

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

//方法：递归+二叉搜索树性质+最近公共祖先性质 
/*
    二叉搜索树:
    
    可以快速地找出树中的某个节点以及从根节点到该节点的路径，例如我们需要找到节点 pp：
    
            我们从根节点开始遍历；
            
            如果当前节点就是 pp，那么成功地找到了节点；
            
            如果当前节点的值大于 pp 的值，说明 pp 应该在当前节点的左子树，因此将当前节点移动到它的左子节点；
            
            如果当前节点的值小于 pp 的值，说明 pp 应该在当前节点的右子树，因此将当前节点移动到它的右子节点。
            
    
    在寻找节点的过程中，我们可以顺便记录经过的节点，这样就得到了从根节点到被寻找节点的路径。

    分别得到了从根节点到 pp 和 qq 的路径之后，我们就可以很方便地找到它们的最近公共祖先了。
    
    显然，pp 和 qq 的最近公共祖先就是从根节点到它们路径上的「分岔点」，也就是最后一个相同的节点。
    
    
    进一步总结： 
    
    若 rootroot 是 pp, qq的 最近公共祖先 ，则只可能为以下情况之一：

    1.pp 和 qq 在 rootroot 的子树中，且分列 rootroot 的 异侧（即分别在左、右子树中）；
    
    2.pp = root，且 qq 在 rootroot 的左或右子树中；
    
    3.qq = root，且 pp 在 rootroot 的左或右子树中；
    
 
    所以，
    
    通过递归对二叉树进行先序遍历，当遇到节点 pp 或 qq 时返回。
    
    从底至顶回溯，当节点 pp, qq在节点 rootroot 的异侧时，节点 rootroot 即为最近公共祖先，则向上返回 rootroot 。

*/

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
{
	TreeNode* res=root;
	if(p->val<root->val&q->val>root->val)
	{
		res= root;//pp 和 qq 在 rootroot 的子树中，且分列 rootroot 的 异侧（即分别在左、右子树中）；
	}	        
	if(p->val==root->val||q->val==root->val)
	{
		res= root;//pp = root，且 qq 在 rootroot 的左或右子树中；qq = root，且 pp 在 rootroot 的左或右子树中；
	}
	if(p->val<root->val&&q->val<root->val)
	{
		res=lowestCommonAncestor(root->left,p,q);//都在左子树中 
	}
	if(p->val>root->val&&q->val>root->val)
	{
		res=lowestCommonAncestor(root->right,p,q);//都在右子树中 
	}
	return res;
        
}