力扣刷题——二叉树的最近公共祖先

题目链接：二叉树的最近公共祖先

题目描述

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

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

题目分析

对于一棵二叉树，要想找到最近的公共祖先节点有很多办法，这里仅介绍其中一种。根据题意，要找最近的公共祖先节点，首先对于一个节点，如果p和q分别在该节点的左右子树中，那么该节点就是pq的最近公共祖先节点。如果两个节点都在某个节点的左子树或者右子树中，那么可以递归进下一个节点进行判断，这里需要注意的是一个节点可能是他自己的祖先节点，即p节点可能也是q节点的祖先节点，需要进行情况判断。代码实现如下：

代码实现

bool Find(TreeNode* root, TreeNode* key)//查找key是否存在于该节点的子树中
{
    
	if (root == nullptr)
	{
    
		return false;
	}
	if (root == key)
	{
    
		return true;
	}
	return Find(root->left, key) || Find(root->right, key);
}


TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
{
    
	bool leftp = Find(root->left, p);
	bool rightp = Find(root->right, p);
	bool leftq = Find(root->left, q);
	bool rightq = Find(root->right, q);
	if (root == p || root == q)
	{
    
		return root;
	}
	else if ((leftp && rightq)||(rightp && leftq))//p和q分别在root的左右子树上
	{
    
		return root;
	}
	else if ((leftp && leftq))//p和q在同一左侧
	{
    
		return lowestCommonAncestor(root->left, p, q);
	}
	else if (rightp && rightq)
	{
    
		return lowestCommonAncestor(root->right, p, q);
	}
	else
	{
    
		return nullptr;
	}

}