第 6 关 | 其实很简单的数与层次遍历问题: 1.青铜挑战—

1. 树的常见概念

树是一个有n个有限节点组成的一个具有层次关系的集合，每个节点有0个或者多个子节点，没有父节点的节点称为根节点，也就是说除了根节点以外每个节点都有父节点，并且有且只有一个。树的种类有很多，我们最常见的就是二叉树，其基本结构如下：

参考以上结构，可以很方便地理解树的以下概念：

节点的度：一个节点含有的子节点的个数称为该节点的度；
树的度：一棵树中，最大的节点的度称为树的度，注意与节点度的区别；
叶子结点或终端节点：度为 0 的节点称为叶子节点；
非终端节点或分支节点：度不为 0 的节点；
双亲节点或者父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
孩子节点或者子节点：一个节点含有的子树的根节点称为该节点的子节点；
兄弟节点：具有相同父节点的节点称为兄弟节点；
节点的祖先：从根到该节点所经分支上的所有节点；
子孙：以某节点为根的子树中任意一个节点都称为该节点的子孙
森林：由 m （m >= 0 ）棵互不相交的树的集合称为森林
无序树：树中任意节点的子节点没有顺序关系，这中树称为无序树，也称为自由树
有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树
二叉树：每个节点最多包含两个子树的树称为二叉树；

2. 树的性质

性质1： 在二叉树的第 i 层最多有 2 ^(i - 1)个节点（i > 0）
性质2： 深度为 k 的二叉树最多有 2 ^ (k - 1) 个节点（k > 0）
性质3： 对于任意一颗二叉树，如果其叶子节点数位 N0，而度数为 2 的节点数为 N2，则 N0 = N2 + 1;
性质4： 具有 n 个节点的完全二叉树的深度为 log2（n + 1）
性质5： 对于完全二叉树，若从上到下、从左到右编号，则编号为 i 的节点，其左孩子编号必定为 2 i，右孩子节点必为 2i+ 1；其双亲编号必为满二叉树。

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

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

这个定义最邪乎了，估计大部分看了之后还不懂什么事完全二叉树，看这个图就可以了：

前面两棵树的 n - 1 层都是满的，最后一层所有节点都集中在左侧区域，而且中间不能有空隙，最后一个为什么不是呢？因为有一节缺了一个左子节点。

3. 树的定义与存储方式

注意

本关讲义我们主要看原理，不写可执行的代码，因此我们只用伪代码，不提供各种语言的定义

定于树的原理和我们前面讲的链表的本质是一样的，只不过多了一个指针，如果是二叉树，只要在链表的定义上增加一个指针就可以了：

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，因此很少使用数组来存储树。

4. 树的遍历方式

我们现在就来看一下树的常见遍历方法。二叉树的遍历方式有层次遍历和深度优先遍历两种:

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

这两种遍历方式不仅仅是二叉树，N叉树也有这两种方式的，图结构也有，只不过我们更习惯叫广度优先和深度优先，本质是一回事。深度优先又有前中后序三种，有同学总分不清这三个顺序，问题就在不清楚这里前中后是相对谁来说的。记住一点：前指的是中间的父节点在遍历中的顺序，只要大家记住前中后序指的就是中间节点的位置就可以了。

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

前序遍历:中左右

中序遍历:左中右

后序遍历:左右中

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

后面的大量算法都和这四种遍历方式有关，有的题目根据角度不同，可以用层次遍历，也可以用一种甚至两种深度优先的方式来实现。

5. 通过序列构造二叉树

5.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

(3) 后序：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) 中序：3 4 8 6 7 5 2 1 10 9 11 15 13 14 12

第一轮：根据前序和中序划分，可以得到根节点为 1 ，然后可以得到第一轮树的结构

第二轮：先看两个序列的第一个数组：

前序： 2 3 4 5 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 8 7 继续划分：前序 4 【 5 6 8 7】中序：4 【8 6 7 5】

第五轮：对 5 6 8 7 继续划分：前序：5 【6 8 7】中序：【8 6 7】5，最后得到的结果如下：

同理可得完整图如下：

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

然后中序和后序也是可以恢复原始序列的，唯一不同的是后序序列的最后一个是根节点，中序也是一样的过程，这里我们可以用以下例子来试一下：

为下为大致过程，第一轮根节点为 5 ，所以，就可以得到左边为【1 4 2】，右边为【7 6 8】，所以第一轮结构如下：

第二轮先对左边进行排序，【1 4 2】，可以得到根节点为 4 ，然后 1 在左边，2 在右边，树的结构如下：

然后另一边也是一样的，结果如下：

5.3. 前序和后序没办法确定

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

(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，但是中间是怎么划分的呢？其他元素哪些属于左子树，哪些属于右子树呢？很明显通过两个序列都不知道，所以前序和后序序列不能恢复二叉树。

如果将上述过程用代码实现该怎么做呢？通过前序和中序构造树就是LeetCode105 题，通过中序和后序构造树就是LeetCode106题，实现过程略微繁琐，感兴趣的同学可以研究一下。

第 6 关 | 其实很简单的数与层次遍历问题: 1.青铜挑战——理解树的结构-灵析社区