📝 题目描述

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

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

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

示例：

示例 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 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

1
2
输入：root = [1,2], p = 1, q = 2
输出：1

提示：

  • 树中节点数目在范围 [2, 105] 内
  • -10^9 <= Node.val <= 10^9
  • 所有 Node.val 互不相同
  • p != q
  • p 和 q 均存在于给定的二叉树中

💡 解题思路

方法一：原地递归✅️

对于一个节点 root，我们可以遍历其左右子树，寻找 p 和 q 分别在哪：

  • 如果其 left 子树和 right 子树都返回了结果，那么一定其中一个是 p 另一个是 q，那么 root 一定为其最近公共祖先。
  • 如果其 left 子树返回结果，但 right 子树返回 nullptr，说明 p 和 q 都不在右子树，答案肯定是 left 子树返回的结果，我们直接返回 left 子树的结果即可。
  • 同理，如果其 right 子树返回结果，但 left 子树返回 nullptr，说明 p 和 q 都不在左子树，答案肯定是 right 子树返回的结果，我们直接返回 right 子树的结果即可。

方法二：逻辑递归

我们递归遍历整棵二叉树，定义 fxf_x​ 表示 xx 节点的子树中是否包含 pp 节点或 qq 节点，如果包含为 true，否则为 false。那么符合条件的最近公共祖先 xx 一定满足如下条件：

(f_{lson}​ && f_{rson​}) ∣∣ ((x = p ∣∣ x = q) && (f_{lson}​ ∣∣ f_{rson}​))

其中 lsonlson 和 rsonrson 分别代表 xx 节点的左孩子和右孩子。f_{lson}​ && f_{rson}​ 说明左子树和右子树均包含 pp 节点或 qq 节点，如果左子树包含的是 pp 节点，那么右子树只能包含 qq 节点，反之亦然，因为 pp 节点和 qq 节点都是不同且唯一的节点，因此如果满足这个判断条件即可说明 xx 就是我们要找的最近公共祖先。再来看第二条判断条件，这个判断条件即是考虑了 xx 恰好是 pp 节点或 qq 节点且它的左子树或右子树有一个包含了另一个节点的情况，因此如果满足这个判断条件亦可说明 xx 就是我们要找的最近公共祖先。

那么这样找出来的公共祖先深度是否是最大的？其实是最大的，因为我们是自底向上从叶子节点开始更新的，所以在所有满足条件的公共祖先中一定是深度最大的祖先先被访问到，且由于 fxf_x​ 本身的定义很巧妙，在找到最近公共祖先 xx 以后，fxf_x​ 按定义被设置为 true ，即假定了这个子树中只有一个 pp 节点或 qq 节点，因此其他公共祖先不会再被判断为符合条件。

下图展示了一个示例，搜索树中两个节点 9 和 11 的最近公共祖先。

参考分步链接：力扣题解。

方法三：存储父节点

从根节点开始遍历整棵树，用一个哈希表记录每个节点的父节点。

然后当我们有了父节点指针，其实这道题就变成了“求两个链表的第一个公共交点”问题：

  • 从 p 开始，顺着父节点往上走，把 p 的所有祖先（包括自己）记录到 ancestors 集合中；
  • 从 q 开始，顺着父节点往上走，它遇到的第一个已经存在于 ancestors 里的节点，就是最近公共祖先。

🔧 代码实现

1、原地递归

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
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 1. 递归终止条件
        // 如果越过叶子节点，或者碰到了 p 或 q，直接返回该节点
        if (root == nullptr || root == p || root == q) {
            return root;
        }
        
        // 2. 递归遍历左右子树
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        
        // 3. 处理当前节点（后序遍历逻辑）
        // 如果左子树和右子树都能找到目标节点，说明 p 和 q 分列在当前节点的两侧
        // 当前节点 root 就是最近公共祖先
        if (left != nullptr && right != nullptr) {
            return root;
        }
        
        // 如果左子树为空，说明 p 和 q 都不在左子树，那么最近公共祖先一定在右子树查找的结果中
        if (left == nullptr) return right;
        
        // 同理，如果右子树为空，返回左子树的查找结果
        if (right == nullptr) return left;
        
        return nullptr; // 理论上题目保证 p 和 q 存在，这句不会走到
    }
};

2、逻辑递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    TreeNode* ans;
    bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr) return false;
        bool lson = dfs(root->left, p, q);
        bool rson = dfs(root->right, p, q);
        if ((lson && rson) || ((root->val == p->val || root->val == q->val) && (lson || rson))) {
            ans = root;
        } 
        return lson || rson || (root->val == p->val || root->val == q->val);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root, p, q);
        return ans;
    }
};

3、存储父节点

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <unordered_map>
#include <unordered_set>
#include <stack>

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        std::unordered_map<TreeNode*, TreeNode*> parent; // 记录子节点到父节点的映射
        std::stack<TreeNode*> st; // 用于深度优先遍历
        
        // 根节点没有父节点
        parent[root] = nullptr;
        st.push(root);
        
        // 遍历二叉树，直到我们找到了 p 和 q 的父节点映射
        while (!parent.count(p) || !parent.count(q)) {
            TreeNode* node = st.top();
            st.pop();
            
            if (node->left) {
                parent[node->left] = node;
                st.push(node->left);
            }
            if (node->right) {
                parent[node->right] = node;
                st.push(node->right);
            }
        }
        
        std::unordered_set<TreeNode*> ancestors; // 记录 p 的所有祖先节点
        
        // 从 p 开始，顺着父节点往上走，把 p 的所有祖先（包括自己）记录下来
        while (p != nullptr) {
            ancestors.insert(p);
            p = parent[p];
        }
        
        // 从 q 开始，顺着父节点往上走。
        // 它遇到的第一个已经存在于 ancestors 里的节点，就是最近公共祖先
        while (q != nullptr) {
            if (ancestors.count(q)) {
                return q;
            }
            q = parent[q];
        }
        
        return nullptr;
    }
};

📊 复杂度分析

1、原地递归

  • 时间复杂度：O(N)O(N)，在最坏情况下，我们需要遍历整棵二叉树的所有节点。
  • 空间复杂度：O(H)O(H)，H 为二叉树的高度。主要消耗在于递归调用栈。最坏情况（树退化为链表）下空间复杂度为 O(N)O(N)，平衡树下为 O(logN)O(log N)。

2、逻辑递归

  • 时间复杂度：O(N)O(N)，其中 N 是二叉树的节点数。二叉树的所有节点有且只会被访问一次。
  • 空间复杂度：O(H)O(H)，H 为二叉树的高度。主要消耗在于递归调用栈。最坏情况（树退化为链表）下空间复杂度为 O(N)O(N)，平衡树下为 O(logN)O(log N)。

2、存储父节点

  • 时间复杂度：O(N)O(N)，遍历二叉树记录父节点需要 O(N)O(N) 时间，之后顺着父节点往上找最多也是 O(N)O(N) 时间。
  • 空间复杂度：O(N)O(N)，哈希表 parent 需要存储所有节点的父节点映射，ancestors 集合也需要额外的空间。

🎯 总结

  • 核心思想：掌握递归的思路。