难度中等1914
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1提示：
- 树中节点数目在范围
[2, 105]内。 -109 <= Node.val <= 109- 所有
Node.val互不相同。 p != qp和q均存在于给定的二叉树中。
思路一：
在解题之前我们先来综述一下出现的情况：
- 如果该树是带有 parent 的三叉链结构 ----> 转化成链表相交的问题
- 如果该树是搜索二叉树结构：
- 如果子节点比根要小，则递归到左子树去找
- 如果子节点比根要大，则递归到右子树去找
- 如果子节点一个比根小，一个比根大，那么他就是最近的公共祖先
- 如果该树是普通二叉树结构（从根开始搜索，查找子节点的位置）：
- 都在左树，则递归到左树去找
- 都在右树，则递归到右树去找
- 如果一个在左，一个在右，那么这个根就是公共祖先
class Solution {
public:
bool FindPath(TreeNode* root, TreeNode* target)
{
if(root == nullptr)
return false;
if(root == target)
return true;
return FindPath(root->left, target) || FindPath(root->right, target);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == p || root == q)
return root;
bool isPleft = FindPath(root->left, p);
bool isPright = !isPleft;
bool isQleft = FindPath(root->left, q);
bool isQright = !isQleft;
if(isPleft && isQleft)
return lowestCommonAncestor(root->left, p, q);
else if(isPright && isQright)
return lowestCommonAncestor(root->right, p, q);
else
return root;
}
};时间复杂度：O(n^2)
思路二：
我们可以发现，其实两个节点的最近公共节点，都是在两个节点的路径之上，那么如果我们得到了这个路径上的节点，我们就可以对其进行查找判断！
我们这里借助栈stack来保存两条路径上的节点，方便我们后续的判断与查找！
- 通过子函数去递归得到两条路径上的节点
- 遇到空则返回false
- 不为空则先将节点入栈，然后判断节点是否为目标节点
- 如果是目标节点的话直接返回，若不是的话则递归到左右子树，继续判断
- 若最后找不到，则将节点出栈，然后返回false
- 有了路径上的节点之后，我们先判断是否两个栈的元素相同，不同则让多的那个栈先pop掉直到两个栈元素相同
- 然后就是分别查找两个栈的栈顶，看看是否节点的指针是相同的，是的话说明就是最近的公共祖先，若没有则不存在
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool FindPath(TreeNode* root, TreeNode* target, stack<TreeNode*>& path)
{
if(root == nullptr)
return false;
path.push(root); //先把节点入栈
if(root == target) //如果是该节点的话直接返回
return true;
//递归到左右子树去找
if(FindPath(root->left, target, path))
return true;
if(FindPath(root->right, target, path))
return true;
//没找到的话说明路径错误，要pop掉
path.pop();
return false;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
stack<TreeNode*> pPath, qPath; //用于存放两条路径的节点
FindPath(root, p, pPath);
FindPath(root, q, qPath);
//让长的那个栈先pop()掉，直到个数相同
if(pPath.size() != qPath.size())
{
while(pPath.size() > qPath.size())
pPath.pop();
while(qPath.size() > pPath.size())
qPath.pop();
}
//查看两个栈里面是否有相同的节点
while(!pPath.empty())
{
if(pPath.top() == qPath.top())
return pPath.top();
pPath.pop();
qPath.pop();
}
return nullptr;
}
};时间复杂度：O(n)，因为只查找了两条路径的长度，最坏就是单支树的情况，且主函数中两个循环也是O(n)，所以总共就是O(n)。
