Eric 的小站

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

1
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
2
输出：5
3
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

1
/**
2
 * Definition for a binary tree node.
3
 * struct TreeNode {
4
 *     int val;
5
 *     TreeNode *left;
6
 *     TreeNode *right;
7
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8
 * };
9
 */
10
class Solution {
11
public:
12
    unordered_map<int, TreeNode*> fa;
13
    unordered_map<int, bool> vis;
14
    void dfs(TreeNode* root) {
15
        if (root->left != nullptr) {
16
            fa[root->left->val] = root;
17
            dfs(root->left);
18
        }
19
        if (root->right != nullptr) {
20
            fa[root->right->val] = root;
21
            dfs(root->right);
22
        }
23
    }
24
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
25
        fa[root->val] = nullptr;
26
        dfs(root);
27
        while(p!=nullptr){
28
            vis[p->val] = true;
29
            p = fa[p->val];
30
        }
31
        while(q!=nullptr){
32
            if(vis[q->val]) return q;
33
            q = fa[q->val];
34
        }
35
        return nullptr;
36

37
    }
38
};