剑指 Offer 68 - II. 二叉树的最近公共祖先

题目描述：

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

//方法：递归+最近公共祖先特点 
/*
    从左右子树分别进行递归，即查找左右子树上是否有p结点或者q结点，就一共有4种情况：
    
    第一种情况：左子树和右子树均找没有p结点或者q结点；或者当前就是p/q; 
    
    第二种情况：左子树上没找到，返回右子树的查找结果；
    
    第三种情况：右子树上没找到，返回左子树的查找结果；
    
    第四种情况：左右子树上均能找到，说明此时的p结点和q结点分居root结点两侧，此时就应当直接返回root结点了。

*/

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
{
	if(root==NULL||root==p||root==q)
	{
		return root;//需要先判空，判相等 
	}
    TreeNode* left=lowestCommonAncestor(root->left,p,q);//查看左子树中是否有p/q 
    TreeNode* right=lowestCommonAncestor(root->right,p,q);//查看右子树中是否有p/q 
	if(left==NULL)
	{
		return right;
	}
	if(right==NULL)
	{
		return left;
	}
	
	return root;       
    
	
}