题目
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
1
2
3
|
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
|
示例 2:
1
2
3
|
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
|
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉树中。
题解
这道题相较于二叉搜索树的最近公共祖先
要稍微复杂一些,因为树不再是搜索树了,而是一颗普通的树,因此无法像上道题那样做特殊的操作。
对于这道题,最为直接的想法是根据树的根节点到p、q两个子节点路径计算出交点,这个交点便是最近的公共祖先。
下面是对应的实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
bool dfs(TreeNode* root, TreeNode* p, TreeNode* q, list<pair<TreeNode*, bool>> &s, TreeNode*& f) {
if (!root)return false;
s.push_back({ root, false });
if (root->val == p->val || root->val == q->val) {
if (s.front().second) {
for (auto itr = s.rbegin(); itr != s.rend(); itr++) {
if (itr->second) {
f = itr->first;
return true;
}
}
}
else {
for (auto &itr : s) {
itr.second = true;
}
}
}
if (dfs(root->left, p, q, s, f))return true;
if (dfs(root->right, p, q, s, f)) return true;
s.pop_back();
return false;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || !p || !q)return nullptr;
TreeNode* f = nullptr;
list<pair<TreeNode*, bool>> s;
dfs(root, p, q, s, f);
return f;
}
|
在上面的实现中,使用了链表s来保存树的路径,当找到一个节点p时,对路径进行标记。当找到另外一个节点q时,查找路径,找到最近的被标记的节点,而这个节点便是最近的公共祖先。
提交后,代码可通过,但耗时排名比较靠后,猜测实现不是最优解,遂查看了讨论,果然自己的实现复杂了,自己的那个想法是最简单的想法,但如果能对这道题做更加详细的分析后,会找到更加方便的方式。
一开始一直按照先序遍历的方式思考,但看了讨论后,发现这道题使用后续遍历会更加合适。首先对左右两个子节点进行递归判断,左子树的返回值记为left,右子树的返回值记为right。这里会分4种情况:
- 如果left和right均有返回值,说明当前的root节点便是最近的公共节点。
- 如果只有left有值,那么说明p、q的公共节点在左子树中,直接返回left。
- 如果只有right有值,那么说明p、q的公共节点在右子树中,直接返回right。
- 如果left和right都为空,那么说明右子树和左子树中都不含有公共节点,直接返回null。
递归的终止条件是,当遇到空节点时返回空,如果当前节点等于p或是等于q,那么就返回当前节点。
对应的实现如下:
1
2
3
4
5
6
7
8
9
10
11
|
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr || root == p || root == q)return root;
auto left = lowestCommonAncestor(root->left, p, q);
auto right = lowestCommonAncestor(root->right, p, q);
if (left == nullptr && right == nullptr) return nullptr;
if (left == nullptr)return right;
if (right == nullptr) return left;
return root;
}
|
上面只有3个条件,没有left和right都为空的情况,实际上这种情况被条件2、3包含了,当left为空时,会返回right,如果right也为空,那么这里返回的就是空。同理,当right为空时,如果left也为空,那么这里也返回空。
另外要注意一点,当root等于p或等于q时就直接返回了,当初看到这里自己会有疑问,那如果q是p的子节点呢?这实际上是没问题的,因为我们从下面的条件中我们可以看到当left或right不为空时直接进行返回。