题目描述

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

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

示例 1：

img

1
2
3
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

具体见题目链接。

算法思路

​ 思考完这道题目的时候我觉得和上一道题挺像的，其实都是从两个节点分别出发，找到公共节表即可（因为从公共最近祖先到根节点肯定必须是一样的）。因此我才去的方式其实跟上一道题的思路是一样的：

  1. 先构造出“链表”，在这里我选择使用数据结构map去记录每个节点和他父节点的映射关系，然后通过队列去遍中序遍历所有的节点即可。
  2. 然后仿照上一题目的思路即可：从两个节点分别遍历这个映射关系，直到两个遍历的值相同即可。
  3. 优化思路：我只想到剪枝。这只针对一些特殊的测试样例，比如题目所给的p，q其实在树的上层，那么实际上不需要遍历到树的下面，提前break即可。优化其实不大，但是半个小时我也只能想到这么个事儿。

代码如下：

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
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        map<int, int> parent;   // 存储每个节点的父亲
        map<int, TreeNode*> self; // 存储节点到自身的映射
        parent[root->val] = INT_MIN;
        self[root->val] = root;
        queue<TreeNode*> search;
        search.push(root);
        int p_flag = 0, q_flag = 0;
        int tmp_val;
        while (!search.empty()) {
            TreeNode *tmp = search.front();
            search.pop();
            if (tmp->left) {
                search.push(tmp->left);
                tmp_val = tmp->left->val;
                parent[tmp_val] = tmp->val;
                self[tmp_val] = tmp->left;
                if (tmp_val == p->val) p_flag = 1;
                if (tmp_val == q->val) q_flag = 1;
            }
            if (tmp->right) {
                search.push(tmp->right);
                tmp_val = tmp->right->val;
                parent[tmp_val] = tmp->val;
                self[tmp_val] = tmp->right;
                if (tmp_val == p->val) p_flag = 1;
                if (tmp_val == q->val) q_flag = 1;
            }
            if (p_flag && q_flag) break;
        }
        // 此时parent存放了所有节点->父节点的映射
        // self节点存储了自身值到自身节点的映射
        int p_val = p->val;
        int q_val = q->val;
        while (p_val != q_val) {
            p_val = (p_val != INT_MIN) ? parent[p_val] : q->val;
            q_val = (q_val != INT_MIN) ? parent[q_val] : p->val;
        }
        return self[p_val];
    }   
};