实用算法题: 最近公共祖先－git reabase实现原理

⛳ 实用算法题系列第一篇 - 最近公共祖先。今天我们来聊一个实用的话题，刷算法题到底有什么用。不知道有多少人和曾经的我一样，觉得刷力扣题的主要作用是为了通过笔试面试，其实很多工具都能抽象成算法。为此，我打算开一个系列用于分享实用的力扣算法，并分析算法的使用场景。这是系列的第一期：最近公共祖先(LCA，Lowest Common Ancestor)。

🐼 先看原题

🦄 思路

直观的想法就是用深度优先搜索，递归遍历树左子树和右子树，找到p, q对应的节点，会遇到四种情况：

1. left, right都为null，即p, q不在树中，返回null（本题可以不考虑这种情况）;
2. left为null, 返回right, right为null, 返回left;
3. left, right都不为null, 说明p, q在根节点的两侧, 返回root;

🎠 代码

var lowestCommonAncestor = function (root, p, q) {
    // root为null，直接返回
    if (root === null) {
        return null;
    }
    // root的值等于其中一个，返回root
    if (root.val === p.val || root.val === q.val) {
        return root;
    }
    // 递归开始
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);
    if (left !== null && right !== null) {
        return root;
    }
    if (left === null && right === null) {
        return null;
    }
    return left === null ? right : left;
};

---

🎈 算法使用场景： git rebase

git常见合并分支主要是merge和rebase两种方式。两者的区别在于，git merge会把分支上的修改与当前的修改合并，提交一个新的合并请求，而git rebase是把之前分支的commit取消，临时保存并接在当前分支的后面。
举个🌰说明：
我们现在已有分支上新建了一个分支myJob。

我们在提交commit时，远程origin也被提交了，出现一下情况：

🧊 git merge的做法：

🧊 git rebase的做法：

git rebase会少提交一个commit，具体原理就是，使用LCA找到两条分支的最新公共祖先，再从origin节点开始，重新提交commit，最后把分支完全合并。

💡 结尾

这是系列的第一篇文章，写完已是晚上10点38分，这对于我一个即将毕业的学生来说，更多的是一种满足感。今天逛知乎看到一个有趣的话题，「有的人出生就在罗马，有的人出生就是牛马」英语表达 Some born Roman，some born for Roman.

引用

用 Git 来讲讲二叉树最近公共祖先
git rebase命令