树专题
先上下本文的提纲,这个是我用 mindmap 画的一个脑图,之后我会继续完善,将其他专题逐步完善起来。
大家也可以使用 vscode blink-mind 打开源文件查看,里面有一些笔记可以点开查看。源文件可以去我的公众号《力扣加加》回复脑图获取,以后脑图也会持续更新更多内容。vscode 插件地址:https://marketplace.visualstudio.com/items?itemName=awehook.vscode-blink-mind
本系列包含以下专题:

一点絮叨

首先亮一下本文的主角 - 树(我的化妆技术还行吧^_^):
树标签在 leetcode 一共有 175 道题。 为了准备这个专题,我花了几天时间将 leetcode 几乎所有的树题目都刷了一遍。
除了 35 个上锁的,1 个不能做的题(1628 题不知道为啥做不了), 4 个标着树的标签但却是图的题目,其他我都刷了一遍。通过集中刷这些题,我发现了一些有趣的信息,今天就分享给大家。

食用指南

大家好,我是 lucifer。今天给大家带来的是《树》专题。另外为了保持章节的聚焦性和实用性,省去了一些内容,比如哈夫曼树,前缀树,平衡二叉树(红黑树等),二叉堆。这些内容相对来说实用性没有那么强,如果大家对这些内容也感兴趣,可以关注下我的仓库 leetcode 算法题解,大家有想看的内容也可以留言告诉我哦~
另外要提前告知大家的是本文所讲的很多内容都很依赖于递归。关于递归的练习我推荐大家把递归过程画到纸上,手动代入几次。等大脑熟悉了递归之后就不用这么辛苦了。 实在懒得画图的同学也可以找一个可视化递归的网站,比如 https://recursion.now.sh/。 等你对递归有了一定的理解之后就仔细研究一下树的各种遍历方法,再把本文看完,最后把文章末尾的题目做一做,搞定个递归问题不大。
文章的后面《两个基本点 - 深度优先遍历》部分,对于如何练习树的遍历的递归思维我也提出了一种方法
最后要强调的是,本文只是帮助你搞定树题目的常见套路,但不是说树的所有题目涉及的考点都讲。比如树状 DP 这种不在本文的讨论范围,因为这种题更侧重的是 DP,如果你不懂 DP 多半是做不出来的,你需要的是学完树和 DP 之后再去学树状 DP。如果你对这些内容感兴趣,可以期待我的后续专题。

前言

提到树大家更熟悉的是现实中的树,而现实中的树是这样的:
而计算机中的树其实是现实中的树的倒影。
计算机的数据结构是对现实世界物体间关系的一种抽象。比如家族的族谱,公司架构中的人员组织关系,电脑中的文件夹结构,html 渲染的 dom 结构等等,这些有层次关系的结构在计算机领域都叫做树。
首先明确一下,树其实是一种逻辑结构。比如笔者平时写复杂递归的时候,尽管笔者做的题目不是树,也会画一个递归树帮助自己理解。
树是一种重要的思维工具
以最简单的计算 fibonacci 数列为例:
1
function fn(n) {
2
if (n == 0 || n == 1) return n;
3
4
return fn(n - 1) + fn(n - 2);
5
}
Copied!
很明显它的入参和返回值都不是树,但是却不影响我们用树的思维去思考。
继续回到上面的代码,根据上面的代码可以画出如下的递归树。
其中树的边表示的是返回值,树节点表示的是需要计算的值,即 fn(n)。
以计算 5 的 fibbonacci 为例,过程大概是这样的(动图演示):
这其实就是一个树的后序遍历,你说树(逻辑上的树)是不是很重要?关于后序遍历咱们后面再讲,现在大家知道是这么回事就行。
大家也可以去 这个网站 查看上面算法的单步执行效果。当然这个网站还有更多的算法的动画演示。
上面的图箭头方向是为了方便大家理解。其实箭头方向变成向下的才是真的树结构。
广义的树真的很有用,但是它范围太大了。 本文所讲的树的题目是比较狭隘的树,指的是输入(参数)或者输出(返回值)是树结构的题目。

基本概念

树的基本概念难度都不大,为了节省篇幅,我这里简单过一下。对于你不熟悉的点,大家自行去查找一下相关资料。我相信大家也不是来看这些的,大家应该想看一些不一样的东西,比如说一些做题的套路。
树是一种非线性数据结构。树结构的基本单位是节点。节点之间的链接,称为分支(branch)。节点与分支形成树状,结构的开端,称为根(root),或根结点。根节点之外的节点,称为子节点(child)。没有链接到其他子节点的节点,称为叶节点(leaf)。如下图是一个典型的树结构:
每个节点可以用以下数据结构来表示:
1
Node {
2
value: any; // 当前节点的值
3
children: Array<Node>; // 指向其儿子
4
}
Copied!
其他重要概念:
  • 树的高度:节点到叶子节点的最大值就是其高度。
  • 树的深度:高度和深度是相反的,高度是从下往上数,深度是从上往下。因此根节点的深度和叶子节点的高度是 0。
  • 树的层:根开始定义,根为第一层,根的孩子为第二层。
  • 二叉树,三叉树,。。。 N 叉树,由其子节点最多可以有几个决定,最多有 N 个就是 N 叉树。

二叉树

二叉树是树结构的一种,两个叉就是说每个节点最多只有两个子节点,我们习惯称之为左节点和右节点。
注意这个只是名字而已,并不是实际位置上的左右
二叉树也是我们做算法题最常见的一种树,因此我们花大篇幅介绍它,大家也要花大量时间重点掌握。
二叉树可以用以下数据结构表示:
1
Node {
2
value: any; // 当前节点的值
3
left: Node | null; // 左儿子
4
right: Node | null; // 右儿子
5
}
Copied!

二叉树分类

  • 完全二叉树
  • 满二叉树
  • 二叉搜索树
  • 红黑树
  • 。。。

二叉树的表示

  • 链表存储
  • 数组存储。非常适合完全二叉树

树题难度几何?

很多人觉得树是一个很难的专题。实际上,只要你掌握了诀窍,它并没那么难。
从官方的难度标签来看,树的题目处于困难难度的一共是 14 道, 这其中还有 1 个标着树的标签但是却是图的题目,因此困难率是 13 / 175 ,也就是 7.4 % 左右。如果排除上锁的 5 道,困难的只有 9 道。大多数困难题,相信你看完本节的内容,也可以做出来。
从通过率来看,只有不到三分之一的题目平均通过率在 50% 以下,其他(绝大多数的题目)通过率都是 50%以上。50% 是一个什么概念呢?这其实很高了。举个例子来说, BFS 的平均通过率差不多在 50%。 而大家认为比较难的二分法和动态规划的平均通过率差不多 40%。
大家不要对树有压力, 树和链表一样是相对容易的专题,今天 lucifer 给大家带来了一个口诀一个中心,两个基本点,三种题型,四个重要概念,七个技巧,帮助你克服树这个难关。

一个中心

一个中心指的是树的遍历。整个树的专题只有一个中心点,那就是树的遍历,大家务必牢牢记住。
不管是什么题目,核心就是树的遍历,这是一切的基础,不会树的遍历后面讲的都是白搭。
其实树的遍历的本质就是去把树里边儿的每个元素都访问一遍(任何数据结构的遍历不都是如此么?)。但怎么访问的?我不能直接访问叶子节点啊,我必须得从根节点开始访问,然后根据子节点指针访问子节点,但是子节点有多个(二叉树最多两个)方向,所以又有了先访问哪个的问题,这造成了不同的遍历方式。
左右子节点的访问顺序通常不重要,极个别情况下会有一些微妙区别。比如说我们想要访问一棵树的最左下角节点,那么顺序就会产生影响,但这种题目会比较少一点。
而遍历不是目的,遍历是为了更好地做处理,这里的处理包括搜索,修改树等。树虽然只能从根开始访问,但是我们可以选择在访问完毕回来的时候做处理,还是在访问回来之前做处理,这两种不同的方式就是后序遍历先序遍历
关于具体的遍历,后面会给大家详细讲,现在只要知道这些遍历是怎么来的就行了。
而树的遍历又可以分为两个基本类型,分别是深度优先遍历和广度优先遍历。这两种遍历方式并不是树特有的,但却伴随树的所有题目。值得注意的是,这两种遍历方式只是一种逻辑而已,因此理论可以应用于任何数据结构,比如 365. 水壶问题 中,就可以对水壶的状态使用广度优先遍历,而水壶的状态可以用一个二元组来表示。
遗憾的是这道题的广度优先遍历解法在 LeetCode 上提交会超时

树的遍历迭代写法

很多小朋友表示二叉树前中后序的递归写法没问题,但是迭代就写不出来,问我有什么好的方法没有。
这里就给大家介绍一种写迭代遍历树的实操技巧,统一三种树的遍历方式,包你不会错,这个方法叫做双色标记法。 如果你会了这个技巧,那么你平时练习大可只用递归。然后面试的时候,真的要求用迭代或者是对性能有特别要求的那种题目,那你就用我的方法套就行了,下面我来详细讲一下这种方法。
我们知道垃圾回收算法中,有一种算法叫三色标记法。 即:
  • 用白色表示尚未访问
  • 灰色表示尚未完全访问子节点
  • 黑色表示子节点全部访问
那么我们可以模仿其思想,使用双色标记法来统一三种遍历。
其核心思想如下:
  • 使用颜色标记节点的状态,新节点为白色,已访问的节点为灰色。
  • 如果遇到的节点为白色,则将其标记为灰色,然后将其右子节点、自身、左子节点依次入栈。
  • 如果遇到的节点为灰色,则将节点的值输出。
使用这种方法实现的中序遍历如下:
1
class Solution:
2
def inorderTraversal(self, root: TreeNode) -> List[int]:
3
WHITE, GRAY = 0, 1
4
res = []
5
stack = [(WHITE, root)]
6
while stack:
7
color, node = stack.pop()
8
if node is None: continue
9
if color == WHITE:
10
stack.append((WHITE, node.right))
11
stack.append((GRAY, node))
12
stack.append((WHITE, node.left))
13
else:
14
res.append(node.val)
15
return res
Copied!
可以看出,实现上 WHITE 就表示的是递归中的第一次进入过程,Gray 则表示递归中的从叶子节点返回的过程。 因此这种迭代的写法更接近递归写法的本质。
如要实现前序、后序遍历,也只需要调整左右子节点的入栈顺序即可,其他部分是无需做任何变化
(前中后序遍历只需要调整这三句话的位置即可)
注:这张示意图的前序和后序画反了
可以看出使用三色标记法,其写法类似递归的形式,因此便于记忆和书写。
有的同学可能会说,这里的每一个节点都会入栈出栈两次,相比普通的迭代入栈和出栈次数整整加了一倍,这性能可以接受么?我要说的是这种时间和空间的增加仅仅是常数项的增加,大多数情况并不会都程序造成太大的影响。 除了有时候比赛会比较恶心人,会卡常(卡常是指通过计算机原理相关的、与理论复杂度无关的方法对代码运行速度进行优化)。反过来看,大家写的代码大多数是递归,要知道递归由于内存栈的开销,性能通常比这里的二色标记法更差才对, 那为啥不用一次入栈的迭代呢?更极端一点,为啥大家不都用 morris 遍历 呢?
morris 遍历 是可以在常数的空间复杂度完成树的遍历的一种算法。
我认为在大多数情况下,大家对这种细小的差异可以不用太关注。另外如果这种遍历方式完全掌握了,再根据递归的思想去写一次入栈的迭代也不是难事。 无非就是调用函数的时候入栈,函数 return 时候出栈罢了。更多二叉树遍历的内容,大家也可以访问我之前写的专题《二叉树的遍历》

小结

简单总结一下,树的题目一个中心就是树的遍历。树的遍历分为两种,分别是深度优先遍历和广度优先遍历。关于树的不同深度优先遍历(前序,中序和后序遍历)的迭代写法是大多数人容易犯错的地方,因此我介绍了一种统一三种遍历的方法 - 二色标记法,这样大家以后写迭代的树的前中后序遍历就再也不用怕了。如果大家彻底熟悉了这种写法,再去记忆和练习一次入栈甚至是 Morris 遍历即可。
其实用一次入栈和出栈的迭代实现递归也很简单,无非就是还是用递归思想,只不过你把递归体放到循环里边而已。大家可以在熟悉递归之后再回头看看就容易理解了。树的深度遍历的递归技巧,我们会在后面的《两个基本点》部分讲解。

两个基本点

上面提到了树的遍历有两种基本方式,分别是深度优先遍历(以下简称 DFS)和广度优先遍历(以下简称 BFS),这就是两个基本点。这两种遍历方式下面又会细分几种方式。比如 DFS 细分为前中后序遍历, BFS 细分为带层的和不带层的
DFS 适合做一些暴力枚举的题目,DFS 如果借助函数调用栈,则可以轻松地使用递归来实现。

BFS 不是 层次遍历

而 BFS 适合求最短距离,这个和层次遍历是不一样的,很多人搞混。这里强调一下,层次遍历和 BFS 是完全不一样的东西。
层次遍历就是一层层遍历树,按照树的层次顺序进行访问。
(层次遍历图示)
BFS 的核心在于求最短问题时候可以提前终止,这才是它的核心价值,层次遍历是一种不需要提前终止的 BFS 的副产物。这个提前终止不同于 DFS 的剪枝的提前终止,而是找到最近目标的提前终止。比如我要找距离最近的目标节点,BFS 找到目标节点就可以直接返回。而 DFS 要穷举所有可能才能找到最近的,这才是 BFS 的核心价值。实际上,我们也可以使用 DFS 实现层次遍历的效果,借助于递归,代码甚至会更简单。
如果找到任意一个满足条件的节点就好了,不必最近的,那么 DFS 和 BFS 没有太大差别。同时为了书写简单,我通常会选择 DFS。
以上就是两种遍历方式的简单介绍,下面我们对两者进行一个详细的讲解。

深度优先遍历

深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历树或图的算法。沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点 v 的所在边都己被探寻过,搜索将回溯到发现节点 v 的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止,属于盲目搜索
深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用拓扑排序表可以方便的解决很多相关的图论问题,如最大路径问题等等。因发明「深度优先搜索算法」,约翰 · 霍普克洛夫特与罗伯特 · 塔扬在 1986 年共同获得计算机领域的最高奖:图灵奖。
截止目前(2020-02-21),深度优先遍历在 LeetCode 中的题目是 129 道。在 LeetCode 中的题型绝对是超级大户了。而对于树的题目,我们基本上都可以使用 DFS 来解决,甚至我们可以基于 DFS 来做层次遍历,而且由于 DFS 可以基于递归去做,因此算法会更简洁。 在对性能有很高要求的场合,我建议你使用迭代,否则尽量使用递归,不仅写起来简单快速,还不容易出错。
DFS 图解:
binary-tree-traversal-dfs

算法流程

  1. 1.
    首先将根节点放入stack中。
  2. 2.
    stack中取出第一个节点,并检验它是否为目标。如果找到目标,则结束搜寻并回传结果。否则将它某一个尚未检验过的直接子节点加入stack中。
  3. 3.
    重复步骤 2。
  4. 4.
    如果不存在未检测过的直接子节点。将上一级节点加入stack中。
    重复步骤 2。
  5. 5.
    重复步骤 4。
  6. 6.
    stack为空,表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。
这里的 stack 可以理解为自己实现的栈,也可以理解为调用栈。如果是调用栈的时候就是递归,如果是自己实现的栈的话就是迭代。

算法模板

一个典型的通用的 DFS 模板可能是这样的:
1
const visited = {}
2
function dfs(i) {
3
if (满足特定条件){
4
// 返回结果 or 退出搜索空间
5
}
6
7
visited[i] = true // 将当前状态标为已搜索
8
for (根据i能到达的下个状态j) {
9
if (!visited[j]) { // 如果状态j没有被搜索过
10
dfs(j)
11
}
12
}
13
}
Copied!
上面的 visited 是为了防止由于环的存在造成的死循环的。 而我们知道树是不存在环的,因此树的题目大多数不需要 visited,除非你对树的结构做了修改,比如就左子树的 left 指针指向自身,此时会有环。再比如 138. 复制带随机指针的链表 这道题需要记录已经复制的节点,这些需要记录 visited 信息的树的题目少之又少
因此一个树的 DFS 更多是:
1
function dfs(root) {
2
if (满足特定条件){
3
// 返回结果 or 退出搜索空间
4
}
5
for (const child of root.children) {
6
dfs(child)
7
}
8
}
Copied!
而几乎所有的题目几乎都是二叉树,因此下面这个模板更常见。
1
function dfs(root) {
2
if (满足特定条件){
3
// 返回结果 or 退出搜索空间
4
}
5
dfs(root.left)
6
dfs(root.right)
7
}
Copied!
而我们不同的题目除了 if (满足特定条件部分不同之外),还会写一些特有的逻辑,这些逻辑写的位置不同,效果也截然不同。那么位置不同会有什么影响,什么时候应该写哪里呢?接下来,我们就聊聊两种常见的 DFS 方式。

两种常见分类

前序遍历和后序遍历是最常见的两种 DFS 方式。而另外一种遍历方式 (中序遍历)一般用于平衡二叉树,这个我们后面的四个重要概念部分再讲。
前序遍历
如果你的代码大概是这么写的(注意主要逻辑的位置):
1
function dfs(root) {
2
if (满足特定条件){
3
// 返回结果 or 退出搜索空间
4
}
5
// 主要逻辑
6
dfs(root.left)
7
dfs(root.right)
8
}
Copied!
那么此时我们称为前序遍历。
后序遍历
而如果你的代码大概是这么写的(注意主要逻辑的位置):
1
function dfs(root) {
2
if (满足特定条件){
3
// 返回结果 or 退出搜索空间
4
}
5
dfs(root.left)
6
dfs(root.right)
7
// 主要逻辑
8
}
Copied!
那么此时我们称为后序遍历。
值得注意的是, 我们有时也会会写出这样的代码:
1
function dfs(root) {
2
if (满足特定条件){
3
// 返回结果 or 退出搜索空间
4
}
5
// 做一些事
6
dfs(root.left)
7
dfs(root.right)
8
// 做另外的事
9
}
Copied!
如上代码,我们在进入和退出左右子树的时候分别执行了一些代码。那么这个时候,是前序遍历还是后序遍历呢?实际上,这属于混合遍历了。不过我们这里只考虑主逻辑的位置,关键词是主逻辑
如果代码主逻辑在左右子树之前执行,那么就是前序遍历。如果代码主逻辑在左右子树之后执行,那么就是后序遍历。关于更详细的内容, 我会在七个技巧 中的前后遍历部分讲解,大家先留个印象,知道有着两种方式就好。
递归遍历的学习技巧
上面的《一个中心》部分,给大家介绍了一种干货技巧《双色遍历》统一三种遍历的迭代写法。 而树的遍历的递归的写法其实大多数人都没问题。为什么递归写的没问题,用栈写迭代就有问题呢? 本质上其实还是对递归的理解不够。那 lucifer 今天给大家介绍一种练习递归的技巧。其实文章开头也提到了,那就是画图 + 手动代入。有的同学不知道怎么画,这里我抛砖引玉分享一下我学习递归的画法。
比如我们要前序遍历一棵这样的树:
1
1
2
/ \
3
2 3
4
/ \
5
4 5
Copied!
图画的还算比较清楚, 就不多解释了。大家遇到题目多画几次这样的递归图,慢慢就对递归有感觉了。

广度优先遍历

树的遍历的两种方式分别是 DFS 和 BFS,刚才的 DFS 我们简单过了一下前序和后序遍历,对它们有了一个简单印象。这一小节,我们来看下树的另外一种遍历方式 - BFS。
BFS 也是图论中算法的一种,不同于 DFS, BFS 采用横向搜索的方式,在数据结构上通常采用队列结构。 注意,DFS 我们借助的是栈来完成,而这里借助的是队列。
BFS 比较适合找最短距离/路径某一个距离的目标。比如给定一个二叉树,在树的最后一行找到最左边的值。,此题是力扣 513 的原题。这不就是求距离根节点最远距离的目标么? 一个 BFS 模板就解决了。
BFS 图解:
binary-tree-traversal-bfs

算法流程

  1. 1.
    首先将根节点放入队列中。
  2. 2.
    从队列中取出第一个节点,并检验它是否为目标。
    • 如果找到目标,则结束搜索并回传结果。
    • 否则将它所有尚未检验过的直接子节点加入队列中。
  3. 3.
    若队列为空,表示整张图都检查过了——亦即图中没有欲搜索的目标。结束搜索并回传“找不到目标”。
  4. 4.
    重复步骤 2。

算法模板

1
const visited = {}
2
function bfs() {
3
let q = new Queue()
4
q.push(初始状态)
5
while(q.length) {
6
let i = q.pop()
7
if (visited[i]) continue
8
if (i 是我们要找的目标) return 结果
9
for (i的可抵达状态j) {
10
if (j 合法) {
11
q.push(j)
12
}
13
}
14
}
15
return 没找到
16
}
Copied!

两种常见分类

BFS 我目前使用的模板就两种,这两个模板可以解决所有的树的 BFS 问题。
前面我提到了“BFS 比较适合找最短距离/路径某一个距离的目标”。 如果我需要求的是最短距离/路径,我是不关心我走到第几步的,这个时候可是用不标记层的目标。而如果我需要求距离某个节点距离等于 k 的所有节点,这个时候第几步这个信息就值得被记录了。
小于 k 或者 大于 k 也是同理。
标记层
一个常见的 BFS 模板,代入题目只需要根据题目微调即可。
1
class Solution:
2
def bfs(k):
3
# 使用双端队列,而不是数组。因为数组从头部删除元素的时间复杂度为 N,双端队列的底层实现其实是链表。
4
queue = collections.deque([root])
5
# 记录层数
6
steps = 0
7
# 需要返回的节点
8
ans = []
9
# 队列不空,生命不止!
10
while queue:
11
size = len(queue)
12
# 遍历当前层的所有节点
13
for _ in range(size):
14
node = queue.popleft()
15
if (step == k) ans.append(node)
16
if node.right:
17
queue.append(node.right)
18
if node.left:
19
queue.append(node.left)
20
# 遍历完当前层所有的节点后 steps + 1
21
steps += 1
22
return ans
Copied!
不标记层
不带层的模板更简单,因此大家其实只需要掌握带层信息的目标就够了。
一个常见的 BFS 模板,代入题目只需要根据题目微调即可。
1
class Solution:
2
def bfs(k):
3
# 使用双端队列,而不是数组。因为数组从头部删除元素的时间复杂度为 N,双端队列的底层实现其实是链表。
4
queue = collections.deque([root])
5
# 队列不空,生命不止!
6
while queue:
7
node = queue.popleft()
8
# 由于没有记录 steps,因此我们肯定是不需要根据层的信息去判断的。否则就用带层的模板了。
9
if (node 是我们要找到的) return node
10
if node.right:
11
queue.append(node.right)
12
if node.left:
13
queue.append(node.left)
14
return -1
Copied!
以上就是 BFS 的两种基本方式,即带层和不带层,具体使用哪种看题目是否需要根据层信息做判断即可。

小结

树的遍历是后面所有内容的基础,而树的遍历的两种方式 DFS 和 BFS 到这里就简单告一段落,现在大家只要知道 DFS 和 BFS 分别有两种常见的方式就够了,后面我会给大家详细补充。

三种题型

树的题目就三种类型,分别是:搜索类,构建类和修改类,而这三类题型的比例也是逐渐降低的,即搜索类的题目最多,其次是构建类,最后是修改类。这一点和链表有很大的不同,链表更多的是修改类。
接下来,lucifer 给大家逐一讲解这三种题型。

搜索类

搜索类的题目是树的题目的绝对大头。而搜索类只有两种解法,那就是 DFS 和 BFS,下面分别介绍。
几乎所有的搜索类题目都可以方便地使用递归来实现,关于递归的技巧会在七个技巧中的单/双递归部分讲解。还有一小部分使用递归不好实现,我们可以使用 BFS,借助队列轻松实现,比如最经典的是求二叉树任意两点的距离,树的距离其实就是最短距离,因此可以用 BFS 模板解决。这也是为啥我说DFS 和 BFS是树的题目的两个基本点的原因。
所有搜索类的题目只要把握三个核心点,即开始点结束点目标即可。

DFS 搜索

DFS 搜索类的基本套路就是从入口开始做 dfs,然后在 dfs 内部判断是否是结束点,这个结束点通常是叶子节点空节点,关于结束这个话题我们放在七个技巧中的边界部分介绍,如果目标是一个基本值(比如数字)直接返回或者使用一个全局变量记录即可,如果是一个数组,则可以通过扩展参数的技巧来完成,关于扩展参数,会在七个技巧中的参数扩展部分介绍。 这基本就是搜索问题的全部了,当你读完后面的七个技巧,回头再回来看这个会更清晰。
套路模板:
1
# 其中 path 是树的路径, 如果需要就带上,不需要就不带
2
def dfs(root, path):
3
# 空节点
4
if not root: return
5
# 叶子节点
6
if not root.left and not root.right: return
7
path.append(root)
8
# 逻辑可以写这里,此时是前序遍历
9
dfs(root.left)
10
dfs(root.right)
11
# 需要弹出,不然会错误计算。
12
# 比如对于如下树:
13
"""
14
5
15
/ \
16
4 8
17
/ / \
18
11 13 4
19
/ \ / \
20
7 2 5 1
21
"""
22
# 如果不 pop,那么 5 -> 4 -> 11 -> 2 这条路径会变成 5 -> 4 -> 11 -> 7 -> 2,其 7 被错误地添加到了 path
23
24
path.pop()
25
# 逻辑也可以写这里,此时是后序遍历
26
27
return 你想返回的数据
Copied!
比如剑指 Offer 34. 二叉树中和为某一值的路径 这道题,题目是:输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。 这不就是从根节点开始,到叶子节点结束的所有路径搜索出来,挑选出和为目标值的路径么?这里的开始点是根节点, 结束点是叶子节点,目标就是路径。
对于求这种满足特定和的题目,我们都可以方便地使用前序遍历 + 参数扩展的形式,关于这个,我会在七个技巧中的前后序部分展开。
由于需要找到所有的路径,而不仅仅是一条,因此这里适合使用回溯暴力枚举。关于回溯,可以参考我的 回溯专题
1
class Solution:
2
def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
3
def backtrack(nodes, path, cur, remain):
4
# 空节点
5
if not cur: return
6
# 叶子节点
7
if cur and not cur.left and not cur.right:
8
if remain == cur.val:
9
nodes.append((path + [cur.val]).copy())
10
return
11
# 选择
12
path.append(cur.val)
13
# 递归左右子树
14
backtrack(nodes, path, cur.left, remain - cur.val)
15
backtrack(nodes, path, cur.right, remain - cur.val)
16
# 撤销选择
17
path.pop(-1)
18
ans = []
19
# 入口,路径,目标值全部传进去,其中路径和path都是扩展的参数
20
backtrack(ans, [], root, target)
21
return ans
Copied!
再比如:1372. 二叉树中的最长交错路径,题目描述:
1
给你一棵以 root 为根的二叉树,二叉树中的交错路径定义如下:
2
3
选择二叉树中 任意 节点和一个方向(左或者右)。
4
如果前进方向为右,那么移动到当前节点的的右子节点,否则移动到它的左子节点。
5
改变前进方向:左变右或者右变左。
6
重复第二步和第三步,直到你在树中无法继续移动。
7
交错路径的长度定义为:访问过的节点数目 - 1(单个节点的路径长度为 0 )。
8
9
请你返回给定树中最长 交错路径 的长度。
10
11
比如:
Copied!
1
此时需要返回 3
2
解释:蓝色节点为树中最长交错路径(右 -> 左 -> 右)。
Copied!
这不就是从任意节点开始,到任意节点结束的所有交错路径全部搜索出来,挑选出最长的么?这里的开始点是树中的任意节点,结束点也是任意节点,目标就是最长的交错路径。
对于入口是任意节点的题目,我们都可以方便地使用双递归来完成,关于这个,我会在七个技巧中的单/双递归部分展开。
对于这种交错类的题目,一个好用的技巧是使用 -1 和 1 来记录方向,这样我们就可以通过乘以 -1 得到另外一个方向。
886. 可能的二分法785. 判断二分图 都用了这个技巧。
用代码表示就是:
1
next_direction = cur_direction * - 1
Copied!
这里我们使用双递归即可解决。 如果题目限定了只从根节点开始,那就可以用单递归解决了。值得注意的是,这里内部递归需要 cache 一下 , 不然容易因为重复计算导致超时。
我的代码是 Python,这里的 lru_cache 就是一个缓存,大家可以使用自己语言的字典模拟实现。
1
class Solution:
2
@lru_cache(None)
3
def dfs(self, root, dir):
4
if not root:
5
return 0
6
if dir == -1:
7
return int(root.left != None) + self.dfs(root.left, dir * -1)
8
return int(root.right != None) + self.dfs(root.right, dir * -1)
9
10
def longestZigZag(self, root: TreeNode) -> int:
11
if not root:
12
return 0
13
return max(self.dfs(root, 1), self.dfs(root, -1), self.longestZigZag(root.left), self.longestZigZag(root.right))
Copied!
这个代码不懂没关系,大家只有知道搜索类题目的大方向即可,具体做法我们后面会介绍,大家留个印象就行。更多的题目以及这些技巧的详细使用方式放在七个技巧部分展开。

BFS 搜索

这种类型相比 DFS,题目数量明显降低,套路也少很多。题目大多是求距离,套用我上面的两种 BFS 模板基本都可以轻松解决,这个不多介绍了。

构建类

除了搜索类,另外一个大头是构建类。构建类又分为两种:普通二叉树的构建和二叉搜索树的构建。

普通二叉树的构建

而普通二叉树的构建又分为三种:
  1. 1.
    给你两种 DFS 的遍历的结果数组,让你构建出原始的树结构。比如根据先序遍历和后序遍历的数组,构造原始二叉树。这种题我在构造二叉树系列 系列里讲的很清楚了,大家可以去看看。
这种题目假设输入的遍历的序列中都不含重复的数字,想想这是为什么。
  1. 1.
    给你一个 BFS 的遍历的结果数组,让你构建出原始的树结构。
最经典的就是 剑指 Offer 37. 序列化二叉树。我们知道力扣的所有的树表示都是使用数字来表示的,而这个数组就是一棵树的层次遍历结果,部分叶子节点的子节点(空节点)也会被打印。比如:[1,2,3,null,null,4,5],就表示的是如下的一颗二叉树:
我们是如何根据这样的一个层次遍历结果构造出原始二叉树的呢?这其实就属于构造二叉树的内容,这个类型目前力扣就这一道题。这道题如果你彻底理解 BFS,那么就难不倒你。
  1. 1.
    还有一种是给你描述一种场景,让你构造一个符合条件的二叉树。这种题和上面的没啥区别,套路简直不要太像,比如 654. 最大二叉树,我就不多说了,大家通过这道题练习一下就知道了。
除了这种静态构建,还有一种很很罕见的动态构建二叉树的,比如 894. 所有可能的满二叉树 ,对于这个题,直接 BFS 就好了。由于这种题很少,因此不做多的介绍。大家只要把最核心的掌握了,这种东西自然水到渠成。

二叉搜索树的构建

普通二叉树无法根据一种序列重构的原因是只知道根节点,无法区分左右子树。如果是二叉搜索树,那么就有可能根据一种遍历序列构造出来。 原因就在于二叉搜索树的根节点的值大于所有的左子树的值,且小于所有的右子树的值。因此我们可以根据这一特性去确定左右子树的位置,经过这样的转换就和上面的普通二叉树没有啥区别了。比如 1008. 前序遍历构造二叉搜索树

修改类

上面介绍了两种常见的题型:搜索类和构建类。还有一种比例相对比较小的题目类型是修改类。
当然修改类的题目也是要基于搜索算法的,不找到目标怎么删呢?
修改类的题目有两种基本类型。

题目要求的修改

一种是题目让你增加,删除节点,或者是修改节点的值或者指向。
修改指针的题目一般不难,比如 116. 填充每个节点的下一个右侧节点指针,这不就是 BFS 的时候顺便记录一下上一次访问的同层节点,然后增加一个指针不就行了么?关于 BFS ,套用我的带层的 BFS 模板就搞定了。
增加和删除的题目一般稍微复杂,比如 450. 删除二叉搜索树中的节点669. 修剪二叉搜索树。西法我教你两个套路,面对这种问题就不带怕的。那就是后序遍历 + 虚拟节点,这两个技巧同样放在后面的七个技巧部分讲解。是不是对七个技巧很期待?^_^
实际工程中,我们也可以不删除节点,而是给节点做一个标记,表示已经被删除了,这叫做软删除。

算法需要,自己修改

另外一种是为了方便计算,自己加了一个指针。
比如 863. 二叉树中所有距离为 K 的结点 通过修改树的节点类,增加一个指向父节点的引用 parent,问题就转化为距离目标节点一定距离的问题了,此时可是用我上面讲的带层的 BFS 模板解决。
动态语言可以直接加属性(比如上面的 parent),而静态语言是不允许的,因此你需要增加一个新的类定义。不过你也可以使用字典来实现, key 是 node 引用, value 是你想记录的东西,比如这里的 parent 节点。
比如对于 Java 来说,我们可以:
1
class Solution {
2
Map<TreeNode, TreeNode> parent;
3
public void dfs(TreeNode node, TreeNode parent) {
4
if (node != null) {
5
parent.put(node, parent);
6
dfs(node.left, node);
7
dfs(node.right, node);
8
}
9
}
10
}
Copied!
简单回顾一下这一小节的知识。
接下来是做树的题目不得不知的四个重要概念。

四个重要概念

二叉搜索树

二叉搜索树(Binary Search Tree),亦称二叉查找树。
二叉搜索树具有下列性质的二叉树:
  • 若左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  • 若右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  • 左、右子树也分别为二叉排序树;
  • 没有键值相等的节点。
对于一个二叉查找树,常规操作有插入,查找,删除,找父节点,求最大值,求最小值。

天生适合查找

二叉查找树,之所以叫查找树就是因为其非常适合查找。
举个例子,如下一颗二叉查找树,我们想找节点值小于且最接近 58 的节点,搜索的流程如图所示:
可以看出每次向下走,都会排除了一个分支,如果一颗二叉搜索树同时也是一颗二叉平衡树的话,那么其搜索过程时间复杂度就是 $O(logN)$。实际上,平衡二叉搜索树的查找和有序数组的二分查找本质都是一样的,只是数据的存储方式不同罢了。那为什么有了有序数组二分,还需要二叉搜索树呢?原因在于树的结构对于动态数据比较友好,比如数据是频繁变动的,比如经常添加和删除,那么就可以使用二叉搜索树。理论上添加和删除的时间复杂度都是 $O(h)$,其中 h 为树的高度,如果是一颗平衡二叉搜索树,那么时间复杂度就是 $O(logN)$。而数组的添加和删除的时间复杂度为 $O(N)$,其中 N 为数组长度。
方便搜索,是二叉搜索树核心的设计初衷。不让查找算法时间复杂度退化到线性是平衡二叉树的初衷
我们平时说的二分很多是数组的二分,因为数组可以随机访问嘛。不过这种二分实在太狭义了,二分的本质是将问题规模缩小到一半,因此二分和数据结构没有本质关系,但是不同的数据结构却给二分赋予了不同的色彩。比如跳表就是链表的二分,二叉搜索树就是树的二分等。随着大家对算法和数据结构的了解的加深,会发现更多有意思的东西^_^

中序遍历是有序的

另外二叉查找树有一个性质,这个性质对于做题很多帮助,那就是: 二叉搜索树的中序遍历的结果是一个有序数组。 比如 98. 验证二叉搜索树 就可以直接中序遍历,并一边遍历一边判断遍历结果是否是单调递增的,如果不是则提前返回 False 即可。
再比如 99. 恢复二叉搜索树,官方难度为困难。题目大意是给你二叉搜索树的根节点 root ,该树中的两个节点被错误地交换。请在不改变其结构的情况下,恢复这棵树。 我们可以先中序遍历发现不是递增的节点,他们就是被错误交换的节点,然后交换恢复即可。这道题难点就在于一点,即错误交换可能错误交换了中序遍历的相邻节点或者中序遍历的非相邻节点,这是两种 case,需要分别讨论。
类似的题目很多,不再赘述。练习的话大家可以做一下这几道题。
大家如果碰到二叉搜索树的搜索类题目,一定先想下能不能利用这个性质来做。

完全二叉树

一棵深度为 k 的有 n 个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为 i(1≤i≤n)的结点与满二叉树中编号为 i 的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。
如下就是一颗完全二叉树:
直接考察完全二叉树的题目虽然不多,貌似只有一道 222. 完全二叉树的节点个数(二分可解),但是理解完全二叉树对你做题其实帮助很大。
如上图,是一颗普通的二叉树。如果我将其中的空节点补充完全,那么它就是一颗完全二叉树了。
这有什么用呢?这很有用!我总结了两个用处:
  1. 1.
    我们可以给完全二叉树编号,这样父子之间就可以通过编号轻松求出。比如我给所有节点从左到右从上到下依次从 1 开始编号。那么已知一个节点的编号是 i,那么其左子节点就是 2 i,右子节点就是 2 1 + 1,父节点就是 (i + 1) / 2。
熟悉二叉堆的同学可能发现了,这就是用数组实现的二叉堆,其实二叉堆就是完全二叉树的一个应用
有的同学会说,”但是很多题目都不是完全二叉树呀,那不是用不上了么?“其实不然,我们只要想象它存在即可,我们将空节点脑补上去不就可以了?比如 662. 二叉树最大宽度。题目描述:
1
给定一个二叉树,编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树(full binary tree)结构相同,但一些节点为空。
2
3
每一层的宽度被定义为两个端点(该层最左和最右的非空节点,两端点间的null节点也计入长度)之间的长度。
4
5
示例 1:
6
7
输入:
8
9
1
10
/ \
11
3 2
12
/ \ \
13
5 3 9
14
15
输出: 4
16
解释: 最大值出现在树的第 3 层,宽度为 4 (5,3,null,9)。
Copied!
很简单,一个带层的 BFS 模板即可搞定,简直就是默写题。不过这里需要注意两点:
  • 入队的时候除了要将普通节点入队,还要空节点入队。
  • 出队的时候除了入队节点本身,还要将节点的位置信息入队,即下方代码的 pos。
参考代码:
1
# Definition for a binary tree node.
2
# class TreeNode:
3
# def __init__(self, x):
4
# self.val = x
5
# self.left = None
6
# self.right = None
7
8
class Solution:
9
def widthOfBinaryTree(self, root: TreeNode) -> int:
10
q = collections.deque([(root, 0)])
11
steps = 0
12
cur_depth = leftmost = ans = 0
13
14
while q:
15
for _ in range(len(q)):
16
node, pos = q.popleft()
17
if node:
18
# 节点编号关关系是不是用上了?
19
q.append((node.left, pos * 2))
20
q.append((node.right, pos * 2 + 1))
21
# 逻辑开始
22
if cur_depth != steps:
23
cur_depth = steps
24
leftmost = pos
25
ans = max(ans, pos - leftmost + 1)
26
# 逻辑结束
27
steps += 1
28
return ans
Copied!
再比如剑指 Offer 37. 序列化二叉树。如果我将一个二叉树的完全二叉树形式序列化,然后通过 BFS 反序列化,这不就是力扣官方序列化树的方式么?比如:
1
1
2
/ \
3
2 3
4
/ \
5
4 5
Copied!
序列化为 "[1,2,3,null,null,4,5]"。 这不就是我刚刚画的完全二叉树么?就是将一个普通的二叉树硬生生当成完全二叉树用了。
其实这并不是序列化成了完全二叉树,下面会纠正。
将一颗普通树序列化为完全二叉树很简单,只要将空节点当成普通节点入队处理即可。代码:
1
class Codec:
2
3
def serialize(self, root):
4
q = collections.deque([root])
5
ans = ''
6
while q:
7
cur = q.popleft()
8
if cur:
9
ans += str(cur.val) + ','
10
q.append(cur.left)
11
q.append(cur.right)
12
else:
13
# 除了这里不一样,其他和普通的不记录层的 BFS 没区别
14
ans += 'null,'
15
# 末尾会多一个逗号,我们去掉它。
16
return ans[:-1]
Copied!
细心的同学可能会发现,我上面的代码其实并不是将树序列化成了完全二叉树,这个我们稍后就会讲到。另外后面多余的空节点也一并序列化了。这其实是可以优化的,优化的方式也很简单,那就是去除末尾的 null 即可。
你只要彻底理解我刚才讲的我们可以给完全二叉树编号,这样父子之间就可以通过编号轻松求出。比如我给所有节点从左到右从上到下依次从 1 开始编号。那么已知一个节点的编号是 i,那么其左子节点就是 2 * i,右子节点就是 2 * i + 1,父节点就是 i / 2。 这句话,那么反序列化对你就不是难事。
如果我用一个箭头表示节点的父子关系,箭头指向节点的两个子节点,那么大概是这样的:
我们刚才提到了:
  • 1 号节点的两个子节点的 2 号 和 3 号。
  • 2 号节点的两个子节点的 4 号 和 5 号。
  • 。。。
  • i 号节点的两个子节点的 2 * i 号 和 2 * i + 1 号。
此时你可能会写出类似这样的代码:
1
def deserialize(self, data):
2
if data == 'null': return None
3
nodes = data.split(',')
4
root = TreeNode(nodes[0])
5
# 从一号开始编号,编号信息一起入队
6
q = collections.deque([(root, 1)])
7
while q:
8
cur, i = q.popleft()
9
# 2 * i 是左节点,而 2 * i 编号对应的其实是索引为 2 * i - 1 的元素, 右节点同理。
10
if 2 * i - 1 < len(nodes): lv = nodes[2 * i - 1]
11
if 2 * i < len(nodes): rv = nodes[2 * i]
12
if lv != 'null':
13
l = TreeNode(lv)
14
# 将左节点和 它的编号 2 * i 入队
15
q.append((l, 2 * i))
16
cur.left = l
17
if rv != 'null':
18
r = TreeNode(rv)
19
# 将右节点和 它的编号 2 * i + 1 入队
20
q.append((r, 2 * i + 1))
21
cur.right = r
22
23
return root
Copied!
但是上面的代码是不对的,因为我们序列化的时候其实不是完全二叉树,这也是上面我埋下的伏笔。因此遇到类似这样的 case 就会挂:
这也是我前面说”上面代码的序列化并不是一颗完全二叉树“的原因。
其实这个很好解决, 核心还是上面我画的那种图:
其实我们可以:
  • 用三个指针分别指向数组第一项,第二项和第三项(如果存在的话),这里用 p1,p2,p3 来标记,分别表示当前处理的节点,当前处理的节点的左子节点和当前处理的节点的右子节点。
  • p1 每次移动一位,p2 和 p3 每次移动两位。
  • p1.left = p2; p1.right = p3。
  • 持续上面的步骤直到 p1 移动到最后。
因此代码就不难写出了。反序列化代码如下:
1
def deserialize(self, data):
2
if data == 'null': return None
3
nodes = data.split(',')
4
root = TreeNode(nodes[0])
5
q = collections.deque([root])
6
i = 0
7
while q and i < len(nodes) - 2:
8
cur = q.popleft()
9
lv = nodes[i + 1]
10
rv = nodes[i + 2]
11
i += 2
12
if lv != 'null':
13
l = TreeNode(lv)
14
q.append(l)
15
cur.left = l
16
if rv != 'null':
17
r = TreeNode(rv)
18
q.append(r)
19
cur.right = r
20
21
return root
Copied!
这个题目虽然并不是完全二叉树的题目,但是却和完全二叉树很像,有借鉴完全二叉树的地方。

路径

关于路径这个概念,leetcode 真的挺喜欢考察的,不信你自己去 leetcode 官网搜索一下路径,看有多少题。树的路径这种题目的变种很多,算是一种经典的考点了。
要明白路径的概念,以及如何解决这种题,只需要看一个题目就好了 124.二叉树中的最大路径和,虽然是困难难度,但是搞清楚概念的话,和简单难度没啥区别。 接下来,我们就以这道题讲解一下。
这道题的题目是 给定一个非空二叉树,返回其最大路径和。路径的概念是:一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。这听起来真的不容易理解,力扣给的 demo 我也没搞懂,这里我自己画了几个图来给大家解释一下这个概念。
首先是官网给的两个例子:
接着是我自己画的一个例子:
如图红色的部分是最大路径上的节点。
可以看出:
  • 路径可以由一个节点做成,可以由两个节点组成,也可以由三个节点组成等等,但是必须连续。
  • 路径必须是”直来直去“的,不能有分叉。 比如上图的路径的左下角是 3,当然也可以是 2,但是 2 比较小。但是不可以 2 和 3 同时选。
我们继续回到 124 题。题目说是 ”从任意节点出发.......“ 看完这个描述我会想到大概率是要么全局记录最大值,要么双递归。
  • 如果使用双递归,那么复杂度就是 $O(N^2)$,实际上,子树的路径和计算出来了,可以推导出父节点的最大路径和,因此如果使用双递归会有重复计算。一个可行的方式是记忆化递归。
  • 如果使用全局记录最大值,只需要在递归的时候 return 当前的一条边(上面提了不能拐),并在函数内部计算以当前节点出发的最大路径和,并更新全局最大值即可。 这里的核心其实是 return 较大的一条边,因为较小的边不可能是答案。
这里我选择使用第二种方法。
代码:
1
class Solution:
2
ans = float('-inf')
3
def maxPathSum(self, root: TreeNode) -> int:
4
def dfs(node):
5
if not node: return 0
6
l = dfs(node.left)
7
r = dfs(node.right)
8
# 选择当前的节点,并选择左右两边,当然左右两边也可以不选。必要时更新全局最大值
9
self.ans = max(self.ans, max(l,0) + max(r, 0) + node.val)
10
# 只返回一边,因此我们挑大的返回。当然左右两边也可以不选
11
return max(l, r, 0) + node.val
12
dfs(root)
13
return self.ans
Copied!
类似题目 113. 路径总和 I

距离

和路径类似,距离也是一个相似且频繁出现的一个考点,并且二者都是搜索类题目的考点。原因就在于最短路径就是距离,而树的最短路径就是边的数目。
这两个题练习一下,碰到距离的题目基本就稳了。

七个技巧

上面数次提到了七个技巧,相信大家已经迫不及待想要看看这七个技巧了吧。那就让我拿出本章压箱底的内容吧~
注意,这七个技巧全部是基于 dfs 的,bfs 掌握了模板就行,基本没有什么技巧可言。
认真学习的小伙伴可以发现了, 上面的内容只有二叉树的迭代写法(双色标记法)两个 BFS 模板 具有实操性,其他大多是战略思想上的。算法思想固然重要,但是要结合具体实践落地才能有实践价值,才能让我们把知识消化成自己的。而这一节满满的全是实用干货ヽ( ̄ ω  ̄( ̄ ω  ̄〃)ゝ。

dfs(root)

第一个技巧,也是最容易掌握的一个技巧。我们写力扣的树题目的时候,函数的入参全都是叫 root。而这个技巧是说,我们在写 dfs 函数的时候,要将函数中表示当前节点的形参写成 root。即:
1
def dfs(root):
2
# your code
Copied!
而之前我一直习惯写成 node,即:
1
def dfs(node):
2
# your code
Copied!
可能有的同学想问:” 这有什么关系么?“。我总结了两个原因。
第一个原因是:以前 dfs 的形参写的是 node, 而我经常误写成 root,导致出错(这个错误并不会抛错,因此不是特别容易发现)。自从换成了 root 就没有发生这样的问题了。
第二个原因是:这样写相当于把 root 当成是 current 指针来用了。最开始 current 指针指向 root,然后不断修改指向树的其它节点。这样就概念就简化了,只有一个当前指针的概念。如果使用 node,就是当前指针 + root 指针两个概念了。
(一开始 current 就是 root)
(后面 current 不断改变。具体如何改变,取决于你的搜索算法,是 dfs 还是 bfs 等)