236. 二叉树的最近公共祖先

题目

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

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

提示：

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

链接

236. 二叉树的最近公共祖先

并查集

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    unordered_map<TreeNode*, TreeNode*> f;
    // 判断y是否是x的祖先
    bool isParent(TreeNode* x, TreeNode* y){
        while(x != f[x]){
            if(x == y) return true;
            x = f[x];
        }
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == p || root == q) return root;
        // 后序遍历构造并查集
        postTraverse(root,NULL);//判断的时候是往上溯源，如果指定root为最上面的祖宗节点，则用while判断的时候判断，则无法判断到root是否满足条件，因此指定NULL为根节点的祖先
        // 从下往上查找p的所有祖先，判断该祖先是否是q的祖先，如果是，则返回祖先节点
        while(p != f[p]){
            if(isParent(q, p))return p;
            p = f[p];
        }
        return NULL;
    }

    // 后续遍历构造并查集
    void postTraverse(TreeNode* root, TreeNode* parent){
        if(!root) return;
        if(root->left) postTraverse(root->left, root);
        if(root->right) postTraverse(root->right, root);
        f[root] = parent;
    }
};
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

前序遍历dfs

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* ans = NULL;
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 思路：深搜，前序遍历暴搜当前二叉树，判断是否包含p和q,在遍历到第一个包含了p和q的节点时，更新结果
        dfs(root, p,q);
        return ans;
    }

    // 判断以root为根的二叉树中，包含p和q的情况，state 0包含q, 
    int dfs(TreeNode* root, TreeNode*p, TreeNode*q){
        if(!root) return 0;
        int state = 0;//默认root不包含p和q
        // 用state统计左右子树的包含p和q的情况
        state |= dfs(root->left, p,q);//暴搜左子树
        state|= dfs(root->right, p,q);//暴搜右子树
        // 统计根节点的包含情况
        if(root == p) state |= 1;//即state |= 01 用十位标记是否包含p
        if(root == q) state |= 2;//即state |= 10 用十位标记是否包含q
        if(state == 3 && !ans) ans = root;//state == 11 如果root这棵二叉树包含了p和q,并且是第一次查找到，则保留答案
        return state;//返回以root为根的二叉树包含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