前言

公共祖先这一类题目，难度不大，但是非常实用，也是面试问到概率比较大的一类题目。

为什么实用呢？主要在Git领域：

git pull这个命令默认是使用merge方式将远端别人的修改拉倒本地，如果带上参数，git pull -r，就会使用rebase的方式将远端修改拉倒本地。
这二者最直观的区别就是：merge 方式合并的分支会看到很多「分叉」，而 rebase 方式合并的分支就是一条直线。但无论哪种方式，如果存在冲突，Git 都会检测出来并让你手动解决冲突。

那么问题来了，Git 是如何检测两条分支是否存在冲突的呢？

以 rebase 命令为例，比如下图的情况，我站在 dev 分支执行 git rebase master，然后 dev 就会接到 master 分支之上：

Git的做法是，首先，找到这两条分支的最近公共祖先 LCA，然后从 master 节点开始，重演 LCA 到 dev 几个 commit 的修改，如果这些修改和 LCA 到 master 的 commit 有冲突，就会提示你手动解决冲突，最后的结果就是把 dev 的分支完全接到 master 上面。

至于Git是如何找到两条不同分支的最近公共祖先，这就是本篇要将的经典算法。

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

公共祖先有两种情况，情况1是确实有第三个节点为公共祖先，情况2是p或者q是公共祖先。

TreeNode* find(TreeNode* root, int val1, int val2){if(root == nullptr) return nullptr;//前序位置if (root->val == val1 || root->val == val2) {// 情况2// root是不是咱们要找的return root;}// root不是咱要找的，咱就去左边找一找TreeNode* left = find(root->left, val1, val2);// root不是咱要找的，咱就去右边找一找TreeNode* right = find(root->right, val1, val2);//后序位置//汇总左右的情况，看咱找到没//情况1if (left != nullptr && right != nullptr) {// 当前节点是 LCA 节点return root;}return left != nullptr ? left : right;
}

把if (root->val == val1 || root->val == val2) 放在后序位置也可以有一样的效果，但是必然会降低效率，后序位置就需要遍历所有节点了。

2.二叉搜索树的最近公共祖先

对应二叉搜索树而言，没有必要老老实实遍历，因为可以利用他左小右大的性质，将当前节点的值与 val1 和 val2 作对比即可判断当前节点是不是 LCA

假设 val1 < val2，那么 val1 <= root.val <= val2 则说明当前节点就是 LCA；若 root.val 比 val1 还小，则需要去值更大的右子树寻找 LCA；若 root.val 比 val2 还大，则需要去值更小的左子树寻找 LCA。

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {// 保证 val1 较小，val2 较大int val1 = min(p->val, q->val);int val2 = max(p->val, q->val);return find(root, val1, val2);}// 在 BST 中寻找 val1 和 val2 的最近公共祖先节点TreeNode* find(TreeNode* root, int val1, int val2) {if (root == nullptr) {return nullptr;}if (root->val > val2) {// 当前节点太大，去左子树找return find(root->left, val1, val2);}if (root->val < val1) {// 当前节点太小，去右子树找return find(root->right, val1, val2);}// val1 <= root->val <= val2// 则当前节点就是最近公共祖先return root;}
};

3.二叉树的最近公共祖先II

和第一题的区别是，如果p或者q不存在树中，要返回null，那么在第一个的find函数中，有这样一段代码：

// 前序位置
if (root.val == val1 || root.val == val2) {// 如果遇到目标值，直接返回return root;
}

现在我们就不能p或者q存在就返回公共节点了，而是需要都存在，那么需要咱定义两个bool类型的变量去记录有没有遍历到p或者q，同时，判断的地方也不要放在前序，为了对二叉树进行完全的搜索，应该把他放在后序：

class Solution {
public:// 用于记录 p 和 q 是否存在于二叉树中bool foundP = false, foundQ = false;TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {TreeNode* res = find(root, p->val, q->val);if (!foundP || !foundQ) {return nullptr;}// p 和 q 都存在二叉树中，才有公共祖先return res;}// 在二叉树中寻找 val1 和 val2 的最近公共祖先节点TreeNode* find(TreeNode* root, int val1, int val2) {if (root == nullptr) {return nullptr;}TreeNode* left = find(root->left, val1, val2);TreeNode* right = find(root->right, val1, val2);// 后序位置，判断当前节点是不是 LCA 节点if (left != nullptr && right != nullptr) {return root;}// 后序位置，判断当前节点是不是目标值if (root->val == val1 || root->val == val2) {// 找到了，记录一下if (root->val == val1) foundP = true;if (root->val == val2) foundQ = true;return root;}return left != nullptr ? left : right;}
};

4.二叉树的最近公共祖先III

这题不太一样，和第一题的区别在于，每个节点都包含其父节点的指针，意思是node* p，p->parent可以找到p的父节点，在这样的背景下找p和q的公共祖先

可以将p和q所在的树枝当做链表

设两个指针分别从两个给定节点出发，如果两个节点不等，则继续往前一步。如果某个节点到达根节点，则跳到另一个节点最初的位置。最终两个指针一定会相遇在交点处,因为到交点处的路径上面指针走过的路程为L1 + L3 + L2,下面的指针走过的路程为L2 + L3 + L1
（更简单的情况是L1 == L2，则直接找到）

class Solution {
public:Node* lowestCommonAncestor(Node* p, Node * q) {Node *a = p, *b = q;while(a != b){if(a == nullptr) a = q;else a = a->parent;if(b == nullptr) b = p;else b = b->parent;}return a;}
};

5.二叉树的最近公共祖先IV

输入的不是p和q，而是一个包含若干节点的列表nodes，返回这些节点的最近公共祖先

和第一题是一样的

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, vector<TreeNode*>& nodes) {// 将列表转化成哈希集合，便于判断元素是否存在unordered_set<int> values;for(auto node : nodes) {values.insert(node->val);}return find(root, values);}// 在二叉树中寻找 values 的最近公共祖先节点TreeNode* find(TreeNode* root, unordered_set<int>& values) {if(root == nullptr) {return nullptr;}// 前序位置if(values.find(root->val) != values.end()){return root;}TreeNode* left = find(root->left, values);TreeNode* right = find(root->right, values);// 后序位置，已经知道左右子树是否存在目标值if (left != nullptr && right != nullptr) {// 当前节点是 LCA 节点return root;}return left != nullptr ? left : right;}
};