题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 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, 10^5]内。 -
-10^9 <= Node.val <= 10^9 -
所有
Node.val互不相同。 -
p != q -
p和q均存在于给定的二叉树中。
思路一
这道题简称 LCA（Lowerest Common Ancestor），是二叉树的经典题目。我最初的思路是两次 dfs 得到从根到两个节点的路径。题目保证给的节点在树中。那么一定有公共祖先 root。得到的两条路径一定都是从 root 开始，然后往下有一段公共区域，最后分叉开走向各自的节点。所以分叉前的最后一个节点就是最近公共祖先。
/**
* 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:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> ppath, qpath;
// dfs找到节点r到target的路径
auto dfs = [&](this auto&& dfs, TreeNode* r, TreeNode* target, vector<TreeNode*>& path) {
if (!r) return;
path.push_back(r);
if (r == target) {
return;
}
if (r->left) dfs(r->left, target, path);
if (r->right) dfs(r->right, target, path);
if (path.back() != target) {
path.pop_back();
}
};
dfs(root, p, ppath);
dfs(root, q, qpath);
// 寻找分叉点
auto pit = ppath.begin(), qit = qpath.begin();
while (*pit == *qit) {
++pit;
++qit;
if (pit == ppath.end() || qit == qpath.end()) {
break;
}
}
return *std::prev(pit);
}
};这个做法使用了辅助空间，因此空间复杂度是 .
思路二
一次递归，直接看注释。
// 根据题目条件，p、q在树中，一定有解。所以最终答案只可能是p、q或者root（指参数）三者中决出。
// 至少树根(ROOT)是一个解。
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// root为空就返回空，root为p或q那么不用再找了。因为再往下不可能同时为p和q的祖先了。
// 不妨假设root=p，再往下都是p的儿子，咋可能是祖先呢。
// 我实际上是在递归找p或q。
if (!root || root == p || root == q) {
return root;
}
// root非空，且既不是p也不是q，分别从左右子树再找。
auto left = lowestCommonAncestor(root->left, p, q);
auto right = lowestCommonAncestor(root->right, p, q);
// 左边既没找到p也没找到q，说明p和q都在右边。返回右边的搜索结果。
if (!left) return right;
// 右边既没找到p也没找到q，说明p和q都在左边。返回左边的搜索结果。
if (!right) return left;
// 左右两边分别找到了p和q，不妨假设left=p，right=q。
// 此时我们是从root找下来的，既然p和q分散在root的两棵子树。
// 当然应该返回root了。
return root;
}