AI summary
type
status
date
slug
summary
category
tags
icon
password

最近公共祖先

如果说笔试的时候经常遇到各种动归回溯这类稍有难度的题目，那么面试会倾向于一些比较经典的问题，难度不算大，而且也比较实用。
本文就用 Git 引出一个经典的算法问题：最近公共祖先（Lowest Common Ancestor，简称 LCA）。
git pull 这个命令我们经常会用，它默认是使用 merge 方式将远端别人的修改拉到本地；如果带上参数 git pull -r，就会使用 rebase 的方式将远端修改拉到本地。
这二者最直观的区别就是：merge 方式合并的分支会看到很多「分叉」，而 rebase 方式合并的分支就是一条直线，具体区别参考：git rebase VS git merge 。但无论哪种方式，如果存在冲突，Git 都会检测出来并让你手动解决冲突。
那么问题来了，Git 是如何检测两条分支是否存在冲突的呢？
以 rebase 命令为例，比如下图的情况，我站在 dev 分支执行 git rebase master，然后 dev 就会接到 master 分支之上：
notion image
这个过程中，Git 是这么做的：
首先，找到这两条分支的最近公共祖先 LCA，然后从 master 节点开始，重演 LCA 到 dev 几个 commit 的修改，如果这些修改和 LCA 到 master 的 commit 有冲突，就会提示你手动解决冲突，最后的结果就是把 dev 的分支完全接到 master 上面。
那么，Git 是如何找到两条不同分支的最近公共祖先的呢？这就是一个经典的算法问题了，下面我来由浅入深讲一讲。

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

给你输入一棵不含重复值的二叉树，以及存在于树中的两个节点 p 和 q，请你计算 p 和 q 的最近公共祖先节点。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
两个节点的最近公共祖先其实就是这两个节点向根节点的「延长线」的交汇点，那么对于任意一个节点，它怎么才能知道自己是不是 p 和 q 的最近公共祖先？
如果一个节点能够在它的左右子树中分别找到 p 和 q，则该节点为 LCA 节点。
定义 f(x) 表示 x 节点的子树中是否包含 p 节点或 q 节点，如果包含为 true，否则为 false。那么符合条件的最近公共祖先 x 一定满足如下条件：
直接看代码：
在 find 函数的后序位置，如果发现 left 和 right 都非空，就说明当前节点是 LCA 节点，即解决了第一种情况：
notion image
因为题目说了 p 和 q 一定存在于二叉树中（这点很重要），所以即便我们遇到 q 就直接返回，根本没遍历到 p，也依然可以断定 p 在 q 底下，q 就是 LCA 节点。
notion image
我们也能发现一个优化的点，就是当我们在左子树找到目标 LCA 节点后，算法并没有结束，而是把右子树又遍历了一遍，这其实是没有必要的。
有前面的铺垫，你是不是想做类似这样的优化？
不行的，因为我们本来就要同时去左子树和右子树寻找，来判断当前节点是不是 LCA。
如果你非要优化，只能用一个外部变量来辅助判断是否已经找到答案，如果已经找到 LCA，则不再继续遍历右子树：
这样，标准的最近公共祖先问题就解决了，接下来看看这个题目有什么变体。

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

依然给你输入一棵不含重复值的二叉树，但这次不是给你输入 p 和 q 两个节点了，而是给你输入一个包含若干节点的列表 nodes（这些节点都存在于二叉树中），让你算这些节点的最近公共祖先。
看起来怪吓人的，实则解法逻辑是一样的，把刚才的代码逻辑稍加改造即可解决这道题：
需要注意的是，这两道题的题目都明确告诉我们这些节点必定存在于二叉树中，如果没有这个前提条件，就需要修改代码了。

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

给你输入一棵不含重复值的二叉树的，以及两个节点 p 和 q，如果 p 或 q 不存在于树中，则返回空指针，否则的话返回 p 和 q 的最近公共祖先节点。
在解决标准的最近公共祖先问题时，我们在 find 函数的前序位置有如果遇到目标值，直接返回的代码。
但对于这道题来说，p 和 q 不一定存在于树中，所以你不能遇到一个目标值就直接返回，而应该对二叉树进行完全搜索（遍历每一个节点），如果发现 p 或 q 不存在于树中，那么是不存在 LCA 的。
哪种写法能够对二叉树进行完全搜索来着？只需要把前序位置的判断逻辑放到后序位置即可：
⚠️
这里的代码比较难理解，要多思考思考，实在不行能背下来也好。

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

给你输入一棵不含重复值的二叉搜索树，以及存在于树中的两个节点 p 和 q，请你计算 p 和 q 的最近公共祖先节点。
把之前的解法代码复制过来肯定也可以解决这道题，但没有用到 BST「左小右大」的性质，显然效率不是最高的。
在标准的最近公共祖先问题中，我们要在后序位置通过左右子树的搜索结果来判断当前节点是不是 LCA ，但对于 BST 来说，根本不需要老老实实去遍历子树，由于 BST 左小右大的性质，将当前节点的值与 val1 和 val2 作对比即可判断当前节点是不是 LCA：
假设 val1 < val2，那么 val1 <= root.val <= val2 则说明当前节点就是 LCA；若 root.val 比 val1 还小，则需要去值更大的右子树寻找 LCA；若 root.val 比 val2 还大，则需要去值更小的左子树寻找 LCA。
代码比较简单：

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

这次输入的二叉树节点比较特殊，包含指向父节点的指针。题目会给你输入一棵存在于二叉树中的两个节点 p 和 q，请你返回它们的最近公共祖先。
由于节点中包含父节点的指针，所以二叉树的根节点就没必要输入了。
这道题其实不是公共祖先的问题，而是单链表相交的问题，你把 parent 指针想象成单链表的 next 指针，题目就变成了：
给你输入两个单链表的头结点 p 和 q，这两个单链表必然会相交，请你返回相交点。
我在前文 双指针秒杀七道链表题 中详细讲解过求链表交点的问题，具体思路在本文就不展开了，直接给出本题的解法代码：
至此，5 道最近公共祖先的题目就全部讲完了，前 3 道题目从一个基本的 find 函数衍生出解法，后 2 道比较特殊，分别利用了 BST 和单链表相关的技巧，希望本文对你有启发。

计算完全二叉树的节点数

222. 完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（从第 0 层开始），则该层包含 1~ 2^h 个节点。
如果让你数一下一棵普通二叉树有多少个节点，这很简单，只要在二叉树的遍历框架上加一点代码就行了。
但是，这题给你一棵完全二叉树，让你计算它的节点个数，你会不会？算法的时间复杂度是多少？
这个算法的时间复杂度应该是 O(logN∗logN)，如果你心中的算法没有达到这么高效，那么本文就是给你写的。
现在回归正题，如何求一棵完全二叉树的节点个数呢？
如果是一个普通二叉树，遍历一遍即可，时间复杂度为 ：
那如果是一棵满二叉树，节点总数就和树的高度呈指数关系，一条路遍历到底即可，时间复杂度为 ：
这里多提一嘴，在二叉树中，度数为 0 的节点与度数为 2 的节点个数关系是什么？
度数是指节点的孩子数，所以有 ，所以有 。
其实很简单对吧，但是保研面试这题考倒我了，当时太紧张了脑子一片空白 🥲
完全二叉树比普通二叉树特殊，但又没有满二叉树那么特殊，计算它的节点总数，可以说是普通二叉树和完全二叉树的结合版，先看代码：
结合刚才针对满二叉树和普通二叉树的算法，上面这段代码应该不难理解，就是一个结合版，但是其中降低时间复杂度的技巧是非常微妙的。
开头说了，这个算法的时间复杂度是 O(log⁡N×log⁡N)，这是怎么算出来的呢？
直觉感觉好像最坏情况下是 O(N×log⁡N) 吧，因为之前的 while 需要 log⁡N的时间，最后要 O(N) 的时间向左右子树递归。
关键点在于，这两个递归只有一个会真的递归下去，另一个一定会触发 hl == hr 而立即返回，不会递归下去。
为什么呢？原因如下：
一棵完全二叉树的两棵子树，至少有一棵是满二叉树：
notion image
总体时间复杂度=递归的次数 x 每次递归的时间复杂度，递归次数就是树的高度 O(logN)，每次递归所花费的时间就是 while 循环，需要 O(logN)，所以总体的时间复杂度是 O(logN*logN)。

惰性展开多叉树

341. 扁平化嵌套列表迭代器

给你一个嵌套的整数列表 nestedList 。每个元素要么是一个整数，要么是一个列表；该列表的元素也可能是整数或者是其他列表。请你实现一个迭代器将其扁平化，使之能够遍历这个列表中的所有整数。
实现扁平迭代器类 NestedIterator ：
  • NestedIterator(List<NestedInteger> nestedList) 用嵌套列表 nestedList 初始化迭代器。
  • int next() 返回嵌套列表的下一个整数。
  • boolean hasNext() 如果仍然存在待迭代的整数，返回 true ；否则，返回 false 。
你的代码将会用下述伪代码检测：
如果 res 与预期的扁平化列表匹配，那么你的代码将会被判为正确。
我们的算法会被输入一个 NestedInteger 列表，我们需要做的就是写一个迭代器类，将这个带有嵌套结构 NestedInteger 的列表「拍平」。
学过设计模式的朋友应该知道，迭代器也是设计模式的一种，目的就是为调用者屏蔽底层数据结构的细节，简单地通过 hasNext 和 next 方法有序地进行遍历。
为什么说这个题目很有启发性呢？因为我最近在用一款类似印象笔记的软件，叫做 Notion（挺有名的）。这个软件的一个亮点就是「万物皆 block」，比如说标题、页面、表格都是 block。有的 block 甚至可以无限嵌套，这就打破了传统笔记本「文件夹」->「笔记本」->「笔记」的三层结构。
回想这个算法问题，NestedInteger 结构实际上也是一种支持无限嵌套的结构，而且可以同时表示整数和列表两种不同类型，我想 Notion 的核心数据结构 block 估计也是这样的一种设计思路。
显然，NestedInteger 这个神奇的数据结构是问题的关键，不过题目专门提醒我们不要尝试去实现它，也不要去猜测它的实现。
为什么？凭什么？是不是题目在误导我？是不是我进行推测之后，这道题就不攻自破了？
你不让推测，我就偏偏要去推测！我反手就把 NestedInteger 这个结构给实现出来：
这玩意儿不就是棵 N 叉树吗？叶子节点是 Integer 类型，其 val 字段非空；其他节点都是 List<NestedInteger> 类型，其 val 字段为空，但是 list 字段非空，装着孩子节点。
notion image
好的，刚才题目说什么来着？把一个 NestedInteger 扁平化对吧？这不就等价于遍历一棵 N 叉树的所有「叶子节点」吗？我把所有叶子节点都拿出来，不就可以作为迭代器进行遍历了吗？
通过 traverse 函数在到达叶子节点的时候把 val 加入结果列表即可：

进阶思路

以上解法虽然可以通过，但是在面试中，也许是有瑕疵的。
我们的解法中，一次性算出了所有叶子节点的值，全部装到 result 列表，也就是内存中，next 和 hasNext 方法只是在对 result 列表做迭代。如果输入的规模非常大，构造函数中的计算就会很慢，而且很占用内存。
一般的迭代器求值应该是「惰性的」，也就是说，如果你要一个结果，我就算一个（或是一小部分）结果出来，而不是一次把所有结果都算出来。
调用 hasNext 时，如果 nestedList 的第一个元素是列表类型，则不断展开这个元素，直到第一个元素是整数类型。
仔细想一下这个过程应该就能理解了，一次只展开一个最内层的 nestedList，不会一次性把所有 nestedList 展开，相当于惰性的 DFS 遍历。
由于调用 next 方法之前一定会调用 hasNext 方法，这就可以保证每次调用 next 方法的时候第一个元素是整数型，直接返回并删除第一个元素即可。
看一下代码：