大家好，我是 lucifer。明天给大家分享 Git 中的算法。
这是本系列的第二篇 –《Git 中的最近公共先人》，第一篇在
这里
<!– more –>
git merge-base
git merge-base A B 能够查找 A 提交和 B 提交的最近公共先人提交。而因为 分支和标签
在 Git 中仅仅是提交的别名，因而 A 和 B 也能够是分支或者标签。
o---o---o---B
/
---o---1---o---o---o---A
如上图的 Git 提交状况，那么 git merge-base A B 会间接返回提交 1 的哈希值。
更多对于 merge-base的用法细节能够参
考官网文档
如何查找公共先人呢？
咱们晓得 git 每次提交，实际上都是新建了一个提交对象，外面记录一些元信息。比方：
- 提交人
- 提交工夫
- 哈希
- 上一次提交的援用
- 。。。
而上一次提交的援用导致了 git 提交是一个链表构造。而 git 反对创立分支，并基于分支
进行开发，因而 git 提交实质上是有向无环图构造。
如上图，咱们基于提交 2 创立了新分支 dev，dev 上开发后咱们能够将其合并到主分支
master。
而当咱们执行合并操作的时候，git 会先应用 merge-base 算法计算最近公共先人。
如果最近公共先人是被 merge 的 commit，则可执行 fast-forward。如下图，咱们将 dev
合并到 master 就能够 fast-forward，就如同没有创立过 dev 分支一样。
最初举一个更简单的例子。如下图，咱们在提交 3 上执行 git merge HEAD 提交 6。会发
生什么？
答案是会找到提交 2。那怎么找到 2 呢?
如果从提交 6 登程一直找父节点，找到 1，并将其放到哈希表中。接下来再从提交 3 登程
同样一直找父节点，如果父节点在哈希表中存在，那么咱们就找到了公共先人，因为是找到
的第一个公共先人，因而其是最近公共先人，间接返回即可。
力扣中刚好有一个题目，咱们来看下。
力扣真题
题目地址(236. 二叉树的最近公共先人)
https://leetcode-cn.com/probl…
题目形容
给定一个二叉树, 找到该树中两个指定节点的最近公共先人。百度百科中最近公共先人的定义为：“对于有根树 T 的两个节点 p、q，最近公共先人示意为一个节点 x，满足 x 是 p、q 的先人且 x 的深度尽可能大（一个节点也能够是它本人的先人）。”示例 1：输出：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输入：3
解释：节点 5 和节点 1 的最近公共先人是节点 3。示例 2：输出：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输入：5
解释：节点 5 和节点 4 的最近公共先人是节点 5。因为依据定义最近公共先人节点能够为节点自身。示例 3：输出：root = [1,2], p = 1, q = 2
输入：1
提醒：树中节点数目在范畴 [2, 105] 内。-109 <= Node.val <= 109
所有 Node.val 互不雷同。p != q
p 和 q 均存在于给定的二叉树中。前置常识
- 二叉树
- 树的遍历
- 哈希表
思路
这道题是给你一个二叉树，让你从二叉树的根登程。
这和 Git 是不一样的，Git 中咱们须要从两个提交节点登程往父节点找。
那是不是意味着下面办法不能够套用了?
也不是。咱们能够在遍历二叉树的时候保护父子关系，而后问题就转化为了后面的问题。
代码
- 语言反对：Java
Java Code:
class Solution {HashMap<Integer, TreeNode> map = new HashMap<>(); // 关系为：key 的父亲是 value
HashSet<TreeNode> set = new HashSet<>();
public void dfs(TreeNode root) {if (root.left != null) {map.put(root.left.val, root);
dfs(root.left);
}
if (root.right != null) {map.put(root.right.val, root);
dfs(root.right);
}
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {dfs(root);
// 从 p 登程，找到 p 的所有先人节点，将其放入 HashSet
while (p != null) {set.add(p);
p = map.get(p.val);
}
// 从 q 登程找到第一个能在 HashSet 中找到的节点，即为最近公共先人
while (q != null) {if (set.contains(q)) {return q;}
q = map.get(q.val);
}
return null;
}
}
复杂度剖析
令 n 为链表长度。
- 工夫复杂度：$O(n)$
- 空间复杂度：$O(n)$
优化
实际上该算法效率并不高。如果咱们仓库提交很多，也就是 N 十分大，也是会慢的。
有没有优化的可能？
当然能够。而且优化的角度有很多。
这不，这位同学就想到了预处理
，链接在这里。
即第一次保护好了节点信息，将其存到文件里，那么当前执行 merge-base，就不须要对已
经解决过的节点进行遍历了。** 实践上，不论 merge-base 多少次，咱们都仅遍历一次节
点 **。
真的这么现实么？
很惋惜不是的。比方我执行了 rebase，reset 等操作扭转了节点怎么解决？这里的细节很
多，我就不在这里开展了。感兴趣的能够退出我的力扣群探讨。
总结
git merge-base 实质上就是一个寻找最近公共先人的算法。
而这个算法最奢侈的就是先从一个节点应用哈希表预处理，而后从另外一个节点开始遍历，
找到的第一个在哈希表中呈现的节点就是最近公共先人。
这个算法也有优化空间，而优化后又须要思考各种边界条件，即缓存生效问题。
以上就是本文的全部内容了。大家对此有何认识，欢送给我留言，我有工夫都会一一查看回
答。更多算法套路能够拜访我的 LeetCode 题解仓库
：https://github.com/azl3979858…。目前曾经 40K star 啦。大家也能够关
注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，致力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你
辨认套路，高效刷题。