日出江花红胜火
春来江水绿如蓝。
C++，求LCA，有两种思路：
- 倍增法
- 根据“若R为P和Q的最近公共祖先，则P和Q一定位于R的不同子树上或者PQ之一等于R”这个理论（简称RPQ理论）
RPQ理论
其实就是一种递归查找的策略，也不太区分是前/中/后序，按理说都可以的。
这里假设是前序，然后对于任一结点R，如果我们分别在其左子树和右子树中，则有三种可能：
- 左右子树中都找到了，返回值非空，这说明PQ分别在左右子树中，，所以直接返回R就好了
- PQ之一等于R，那说明R就是LCA，直接返回R就好了
- 只有左子树找到了，那就说明PQ在左子树中，那我们继续递归查找左子树就好了，直到情况1,2出现
- 同理，继续递归查找右子树，直到情况1,2出现
所以，就能写出如下代码：
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;
else if (left) return lowestCommonAncestor(root->left, p, q);
else return lowestCommonAncestor(root->right, p, q);
}
};
细心的小伙伴就发现了，第5行和第8行以及第6行和第6行，不是重复了吗？？？
对，就是重复了，也就是说我们已经找过左右子树了，不用重复查找。
所以最终代码就变成了这样：
/**
* 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这个属性。
/**
* 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 (p->left == q || p->right == q) return p;
if (q->left == p || q->right == p) return q;
unordered_map<int, TreeNode *> level_map;
level(root, 1, level_map);
int indexp = findbyvalue(level_map, p);
int indexq = findbyvalue(level_map, q);
while (indexp != indexq && indexq >= 1 && indexp >= 1) {
if (indexp < indexq) indexq /= 2;
else if (indexp > indexq) indexp /= 2;
}
return level_map[indexp];
}
void level(TreeNode *root, int index, unordered_map<int, TreeNode *> &level_map) {
if (root == nullptr) return ;
level_map[index] = root;
level(root->left, index * 2, level_map);
level(root->right, index * 2 + 1, level_map);
}
private:
int findbyvalue(unordered_map<int, TreeNode *> &level_map, TreeNode *root) {
for (auto it : level_map) {
if (it.second == root)
return it.first;
}
return -1;
}
};
