49 二叉树的最近公共祖先

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

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

一共两种情况：一种是p/q是最近公共祖先，那么p和q一定在一侧，以其祖先节点往左右找一定只有left or right是有值的；另一种是除p和q以外某个点是祖先，其left和right一定是p or q，所以都不为空

git的pull merge原理

提示：

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

题解1 递归（左神）

/**
 * 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(! root || root == p || root == q){
            return root;
        }
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if(left && right) return root;

        return left ? left : right;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

题解2 哈希表

class Solution {
    // 每个结点值不同，所以第一个元素可以用int
    unordered_map<int, TreeNode*> fatherNodes;
    unordered_map<int, bool> visited;
public:
	// DFS 记录父链 
    void dfs(TreeNode* root){
        if(root->left) {
            fatherNodes[root->left->val] = root;
            dfs(root->left);
        }
        if(root->right){
            fatherNodes[root->right->val] = root;
            dfs(root->right);
        }
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        fatherNodes[root->val] = nullptr;

        dfs(root);
		// visited
        while(p){
            visited[p->val] = true;
            p = fatherNodes[p->val];
        }
        while(q){
            if(visited[q->val]) 
                return q;
            q = fatherNodes[q->val];
        }

        return nullptr;
    }
};
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