LCA In Tree

发表于 | 分类于

LCA In Tree

题目描述：

给定一棵树和树中的两个节点，要求返回这两个节点的最近公共祖先节点.

例子：

leetcode上有两道题目是关于公共祖先问题的，具体描述可以看LeetCode235和LeetCode236

解题思路：

主要的思路是这样的：我们遍历当前节点为cur，如果cur为空，或者cur是等于目标结点之一的情况下，我们就直接返回这个节点即可；如果不是的情况下，我们继续下一层的遍历，记left是左侧返回的结果，right是右侧的返回的结果；如果左侧和右侧均不为空，则说明在当前节点的情况下，左侧或者右侧找到了两个目标节点，则当前节点即为最近的公共祖先；如果其中一个为空的情况下；说明某侧找到了其中的一个节点或者当前的cur即为公共祖先且为目标节点中的一个。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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 == NULL || root == q || root == p)
            return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        
        if (left != NULL && right != NULL)
            return root;
        
        return left != NULL ? left : right;
        
    }
};

解法2

当然在需要多次查询公共祖先的情况下，我们可以采用另外一种方法来查找树的公共祖先。首先我们构造一个哈希表，表中的key是某个节点，value是其父节点。当要查询a1和a2的公共祖先的时候，先从表中查询到从a1到根节点上的所有节点构成父节点集合，然后我们开始从a2查找是否在该集合中，存在即为祖先节点，不存在则继续向上查找。

代码如下：

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
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        map<TreeNode*, TreeNode*> hash;
        hash[root] = NULL;
        helper(root, hash);
        set<TreeNode*> ancestor;
        ancestor.insert(p);
        TreeNode* cur = p;
        while(cur != NULL){
            ancestor.insert(hash[cur]);
            cur = hash[cur];
        }
        cur = q;
        while(ancestor.find(cur) == ancestor.end()){
            cur = hash[cur];
        }
        return cur;
        
    }
    void helper(TreeNode* root, map<TreeNode*, TreeNode*>& hash){
        if (!root) return;
        if (root->left)
            hash[root->left] = root;
        if (root->right)
            hash[root->right] = root;
        helper(root->left, hash);
        helper(root->right, hash);
    }
};