题目

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

百度百科中最近公共祖先的定义为:“对于有根树 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种情况:

  1. 如果left和right均有返回值,说明当前的root节点便是最近的公共节点。
  2. 如果只有left有值,那么说明p、q的公共节点在左子树中,直接返回left。
  3. 如果只有right有值,那么说明p、q的公共节点在右子树中,直接返回right。
  4. 如果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不为空时直接进行返回。