15.面试算法-树基础

1. 树基础

树在工程中有非常广泛的应用，在算法中也是一个极为庞大的体系，我们前面链表的文章中说过“没学会反转，链表相当于白学”，现在再加一句“没学会树的问题，算法相当于没学”。

本文我们将系统地学习相关问题。在算法中，树的考察点主要包括四个方面：层次遍历以及拓展问题，前后序遍历与拓展问题、中序遍历与搜索树问题、堆和平衡树相关问题。

层次遍历就是从根节点开始一层层遍历所有节点，问题本身不难，但是很多人没认真学过，以至于面试遇到这类问题就直接走人，实在可惜。层次遍历的思想同样适用于图以及更高阶的算法场景中，这类问题在笔试中也经常出现，但是不要因为没学就觉得难。

树的前中后序的根基都是递归，我们会先研究递归相关的问题。递归到底怎么执行的，怎么写递归的代码等等。而且递归也是很多高级算法的骨架。回溯主要是解决暴力枚举也无法解决的场景，回溯就是递归的拓展和优化。动态规划和贪心则是解决具有最优子问题的场景，也是递归的拓展。所以不会递归就没有能力学习回溯、贪心和动态规划这些高级主题。

二叉树的深度优先遍历有三种：前中后序，从题目角度来看，前序和后序的题目不易区分，所以干脆不分，我们专注研究相关问题该怎么解决。

中序遍历的特点非常明显，如果将二分查找的搜索结构画成图，会发现和二叉树的中序搜索完全一样，因此经常基于二叉树的中序遍历来构建搜索树。不管是从思维过程还是代码实现，你都会发现二分查找和搜索树基本一样。

树的前中后序都是递归的最佳实践，排序里最重要的两个算法是快速排序和归并排序，而前者本质就是二叉树的前序遍历，后者就是后序遍历。

如果对中序搜索树不加管理，很可能会退化成查找效率很低的线性结构，因此如何保持树的平衡在应用中，特别是 jdk等底层框架中的重要问题，由此出现了平衡二叉树的概念，简单来说就是每次增加或者删除元素的时候都保证整个树的平衡，这就是AVL要研究的问题。

但是AVL的最大问题是频繁更新节点导致处理效率太低，所以就产生了红黑树这种不完全平衡的二叉树，实现维护性能与查找效率的折中。

堆也是一种特殊的树结构，能够非常好的处理流数据、超大规模数据下的查找问题，特别是与K相关的算法，有些题甚至只能使用堆算法进行。好消息是这种算法是非常有限的，只要学会了就再也不用怕这种问题了。

从重要性程度来说，各个核心问题的关系应该是这样的：前后序问题>层序遍历问题>堆算法>中序和搜索树问题>平衡树>红黑树。

1.1 常见概念

树是一个有n个有限节点组成一个具有层次关系的集合，每个节点有0个或者多个子节点，没有父节点的节点称为根节点，也就是说除了根节点以外每个节点都有父节点，并且有且只有一个。

树的种类比较多，有二叉树，红黑树，AVL树，B树，哈夫曼树，字典树等等。堆也可以把它看成是一棵树，树的这么多种类中，我们最常见的应该是二叉树了，下面我们来看一下它的结构。

树有一些特有的概念，列表如下，这个在所有的数据结构教材或者算法书里都会大讲特讲。我们罗列了常见的概念：

1. 节点的度：一个节点含有的子节点的个数称为该节点的度;
2. 叶节点或终端节点：度为0的节点称为叶节点;
3. 非终端节点或分支节点：度不为0的节点;
4. 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点;
5. 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点;
6. 兄弟节点：具有相同父节点的节点互称为兄弟节点;
7. 树的度：一棵树中，最大的节点的度称为树的度;
8. 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推;
9. 树的高度或深度：树中节点的最大层次;
10. 节点的祖先：从根到该节点所经分支上的所有节点;
11. 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
12. 森林：由m(m>=0)棵互不相交的树的集合称为森林;
13. 无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树;
14. 有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树;
15. 二叉树：每个节点最多含有两个子树的树称为二叉树;

1.2 满二叉树和完全二叉树

满二叉树和完全二叉树是经常晕的问题，我们有必要看一下。

满二叉树：如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这棵二叉树为满二叉树。

这棵二叉树为满二叉树，也可以说深度为k=4，有2^k-1=15个节点的二叉树。

完全二叉树的定义如下:在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。

这个定义最邪乎了，估计大部分看了之后还是不懂什么是完全二叉树。一图胜千言，看这个图就知道了：

前面两棵树的前n-1层都是满的，最后一层所有节点都集中在左侧区域，而且节点之间不能有空隙。最后一个为什么不是？因为有一节点缺了一个左子节点，你能找到是哪个吗？如果要将其变成完全二叉树，你有几种方法？

在完全二叉树中，若最底层为第 h=4 层，则该层包含 1~ 2^(h -1)个节点。

二叉树之后我会介绍各种各样的树，例如我会专门分析优先级队列和堆的问题。其实优先级队列就是一个堆，而堆就是一棵完全二叉树，同时保证父子节点的顺序关系。这就将基本内容串联起来了，邪乎的优先级队列就是个完全二叉树，这样介绍起来比说一堆废话强多了。

1.3 树的定义与存储方式

在java中定义树还是比较容易的，如果是二叉树，我们只要在链表的定义上增加一个指针就可以了：

public class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
}

这里本质上就是有两个引用，分别指向两个位置，为了便于理解，我们分别命名为左和右。如果是N叉树该如何定义呢？其实就是每个节点最多可以有N个指针指向其他地方，这是不用left和right，使用一个List就可以了，也就是：

public class TreeNode {
	int val;
	List<TreeNode> nodes;
}

上面的这种结构是业务的角度定义的，也就是给人看的。在底层存储方面，二叉树可以使用链式结构存储，也可以使用顺序结构存储。链式存储方式就用指针，顺序存储的方式就是用数组。如果用数组存储的元素在内存是连续分布的，而链式存储则是通过指针把分布在散落在各个地址的节点串联一起。

链式存储相对比较好理解，如下图：

那么数组是如何存储呢?其实就是用数组来存储二叉树，顺序存储的方式如图:

用数组来存储二叉树如何遍历的呢?如果父节点的数组下表是i，那么它的左孩子就是i * 2 + 1，右孩子就是 i * 2 + 2。但是用链式表示的二叉树，更有利于我们理解，所以一般我们都是用链式存储二叉树。所以大家要了解，用数组依然可以表示二叉树。

使用数组存储的最大不足是可能存在大量的空间浪费。例如上图中如果b分支没有，那么数组种1 3 4 位置都要空着，但是整个数组的大小仍然是7，因此在很多源码框架中很少使用数组来存储树。

1.4 常见的树

1.4.1 二叉树和N叉树

我们常见的树有哪几种呢？我们最熟悉的树是二叉树，但是你在工程中有定义过二叉树结构吗？反正我没有，原因是几乎无法扩展，如果有三种情况该怎么办呢？我们更多使用List的方式来定义N叉树的结构，这样不管增加还是减少情况都非常灵活。不过我们在手写算法时N叉树反而极少，会大量研究二叉树的问题，原因也很简单，二叉树“麻雀虽小五脏俱全”，递归、迭代等思维通过二叉树就能很好考察了，代码也短小精湛，非常适合面试。这也看到了面试算法与工程算法的区别。

1.4.2 平衡树和AVL树

我们还经常听到平衡树或者AVL树的概念。这又是什么意思呢？我们先看两个二叉树，请问哪个查找效率更高呢？

我们会觉得左侧更高，右侧的更低，为什么呢？

因为查找的次数取决于树的深度，左侧9个数最多查四次就能找到，而右侧可能需要8次。如果我们对树的结构不加维护，随着插入和删除元素变多就可能退化成右侧的样子，所以我们要想办法不断调整树的结构，使其深度尽量少。最佳的情况是如果任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过1，这个过程就是让树平衡。满足这个要求的树就叫平衡树。AVL全名是平衡二叉查找树，可以理解为就是平衡二叉树的意思。

为了保证查找效率，我们每次插入或者删除元素的时候都会测试当前树是否为平衡树，如果不是就要进行调整，虽然这样会让查找效率最高，但是频繁的操作树导致整体性能非常低。

“水至清则无鱼”，我们能否在查找效率和维护平衡之间找到折中方案，也就非完全平衡二叉树呢？有！红黑树就是，而红黑树在java的Hashmap中就用了，这个也经常在面试过程中遇到，所以分析其原理对java程序员是非常必要的。

目前网络上大量充斥红黑树的几个原则，不知道你是否看懂，反正我是没看懂，因为根本就没有说为什么会有这几条规则，内在本质是什么，为什么实现了查找效率与维护效率的折中？理解不彻底，面试背给面试官听有意义吗？这里的关键是红黑树其实就是在用二叉树实现2-3树或者2-3-4树，也就是一个节点可以有2个或者3个值，因此树的深度会更短。不过呢，2-3或者2-3-4树实现过于麻烦，红黑就是使用二叉树来实现2-3或者2-3-4树的，具体怎么做，我们后面专门讨论。

1.4.3 堆

堆也是我们经常听到的结构，与JVM里的堆不同，在算法里讨论的堆更加简洁一些。根据比较的是大还是小的不
同，有大顶堆和小顶堆两种。堆能完美解决很多特定的问题，例如在流数据中找第K大元素，以及将K个线性表合并等等。这些算法的特点和解决的套路都是固定的，例如查找的规则是“查小用大，查大用小”，排序则是“升序用小，
降序用大”，因此只要学会就不怕再考了，具体怎么回事我们后面详细讨论。

1.4.4 B+树

B树和B+树也是我们经常听到的结构，其中B+树最典型的应用就是MySQl数据库的InnoDB引擎里的索引。B+树的特点是一个结点可以存N个值，而且非叶子结点只存索引不存数据。叶子结点才保存数据，叶子结点直接还会通过链表相连接。这些特点看似很零散，但是学清楚之后几年都不会忘。

B+树是理解Mysql的根基，例如如果要理解Mysql几种事务的实现原理，就必须理解索引怎么工作的，要理解索引就必须明白B+树的特点。

还有一个哈夫曼树，这个在编码压缩中应用比较多，本身不复杂，相关算法题也不多，所以我们也不介绍。

1.5 树的遍历方式

任何数据结构只要掌握其增删改查的方法就掌握一大半了。我们现在就来看一下树的查找方法，也就是常说的遍历方法。

二叉树的遍历方式有层次遍历和深度优先遍历两种，而深度优先又有前中后三种，大量的题目都与这几种遍历方式密切相关，或者说就是其变形和拓展。

二叉树主要有两种遍历方式：

• 深度优先遍历：先往深走，遇到叶子节点再往回走。
• 广度优先遍历：一层一层的去遍历，一层访问完再访问下一层。

这两种遍历方式不仅仅是二叉树，N叉树也有这两种方式的。图结构也有，只不过我们更习惯叫广度优先和深度优先，本质是一回事。

深度优先遍历：又分为前序、中序和后序三种类型。由于其特性，可以使用递归和迭代两种方式，因此一下就产生了6道算法题：

前序遍历（递归法，迭代法）
中序遍历（递归法，迭代法）
后序遍历（递归法，迭代法）
广度优先遍历
层次遍历（迭代法）

在深度优先遍历中有人总分不清这三个顺序，经常搞混，其实是不清楚这里前中后是相对谁来说的。只要大家记住前中后序指的就是中间节点的位置就可以了。

看如下中间节点的顺序，就可以发现，访问中间节点的顺序就是所谓的遍历方式

前序遍历：中左右
中序遍历：左中右
后序遍历：左右中

大家可以对着如下图，看看自己理解的前后中序有没有问题。

之前我们讲栈与队列的时候说栈是递归的一种实现结构，这意味着前中后序遍历都可以借助栈自己来迭代实现。这里的区别就是递归是系统帮我们管理了栈，而迭代是要我们自己来维护栈结构。

广度优先遍历一般使用队列来实现，队列的主要功能是缓存某层还没来得及处理的结点的，也就说队列这里只是一个缓存的角色。因此我们前面的文章中也说单纯考察队列的题目非常少，更多是在需要临时缓存一些尚未处理元素的时候将队列作为一个工具使用。而树的层次遍历和高级算法中的广度优先问题恰恰需要这么一个结构，因此这里题目里几乎都可以看到队列的身影。

1.6 恢复二叉树

前面我们已经介绍了前中后序遍历的基本过程，现在我们看一个更为复杂的例子，并且分析如果通过给出的序列来恢复原始二叉树。

这正好对应了LeetCode105和106的题，我们这里先要明白如何通过遍历序列来复原原始二叉树，后面再看如何实现，看三个序列：

(1) 前序：1 2 3 4 5 6 8 7 9 10 11 12 13 15 14
(2) 中序：3 4 8 6 7 5 2 1 10 9 11 15 13 14 12
(3) 后序：8 7 6 5 4 3 2 10 15 14 13 12 11 9 1

1.6.1前中序列复原二叉树

我们先看如何通过前中序列复原二叉树：

(1) 前序：1 2 3 4 5 6 8 7 9 10 11 12 13 15 14
(2) 中序：3 4 8 6 7 5 2 1 10 9 11 15 13 14 12

第一轮：

我们知道前序第一个访问的就是根节点，所以根节点就是1。

中序遍历的特点是根节点的左子树的元素都在根节点的左侧，右子树的元素都在根节点的右侧，从中序遍历序列我们可以划分成如下结构：

中序序列划分：
[3 4 8 6 7 5 2] 1 [ 10 9 11 15 13 14 12]
前序序列划分为：
1 [2 3 4 5 6 8 7 ] [9 10 11 12 13 15 14]

上面前序序列第一个括号里的都是左子树的元素，第二个括号一定都是右子树的元素。

那这里怎么知道两个括号从哪里分开呢？是参照中序的两个数组划分的。我们看到前序中7之前的元素都在中序第一个数组中，9之后的所有元素就在第二个数组种，所以我们从7和9之间划分。

由此，画图表示一下此时知道的树的结构为：

第二轮：

我们先看两个序列的第一个数组：

前序：2 3 4 5 6 8 7
中序：3 4 8 6 7 5 2

此时又可以利用上面的结论划分了：

根节点是2，然后根据2在中序中的位置可以划分为：

前序：2 [3 4 5 6 8 7 ]
中序： [3 4 8 6 7 5 ] 2

所以此时的树结构为：

第三轮：

对 3 4 5 6 8 7 继续划分：

前序：3 [4 5 6 8 7 ]
中序：3 [4 8 6 7 5 ]

此时结构为：

第四轮：

对 4 5 6 8 7 继续划分：

前序：4 [5 6 8 7 ]
中序：4 [8 6 7 5 ]

此时树为：

第五轮：

对 5 6 8 7 继续划分：

前序：5 [6 8 7]
中序： [8 6 7] 5

此时树为：

直接画最终结果吧：

同理，对于序列[ 10 9 11 15 13 14 12]，我们也可以逐步划分，最终结果为：

1.6.2 通过中序和后序序列恢复二叉树

通过中序和后序也能恢复原始序列的，唯一的不同是后序序列的最后一个是根节点，中序的处理也是上面一样的过程：

前序：1 2 3 4 5 6 8 7 9 10 11 12 13 15 14
中序：3 4 8 6 7 5 2 1 10 9 11 15 13 14 12
后序：8 7 6 5 4 3 2 10 15 14 13 12 11 9 1

大家可以自行试一试，我们就不再赘述。

问题：为什么前序和后序不能恢复二叉树

既然上面两种都行，那为什么前序和后序不行呢？我们看下面的例子：

(1) 前序：1 2 3 4 5 6 8 7 9 10 11 12 13 15 14
(2) 后序：8 7 6 5 4 3 2 10 15 14 13 12 11 9 1

根据上面的说明，我们通过前序可以知道根节点是1，通过后序也能知道根节点是1，但是中间是怎么划分的呢？其他元素哪些属于左子树，哪些属于右子树呢？很明显此时是不知道的。
所以前序和后序序列不能恢复二叉树。