二叉树

二叉树
完全二叉树与满二叉树
二叉树的遍历
深度优先遍历
- 深度优先遍历的直观感受
广度优先遍历
- 广度优先遍历的直观感受
- 广度优先遍历需要借助「队列」实现
例 1：「力扣」第 102 题：二叉树的层序遍历
「深度优先遍历」与「广度优先遍历」的比较
练习
总结

树的简介
「树」的特点是：除了根结点以外，其它结点都有唯一的父亲结点。「树」还可以递归定义：

树是有限结点的集合；
这个集合或者是空集，或者其中有一个称为根结点的特殊结点，其余结点分别属于不同的 不相交 的树，这些树分别是原始树（或称作原始树的根结点）的子树。

很多树的问题都可以使用「递归」方法解决。树形结构还有一个重要的特征区别于其它复杂的数据结构的特点：在树形结构里，能看到非常明显的 层次结构，用于表示各种常见的层次关系。

二叉树是最简单的树形结构：如果一棵树中每个结点 至多有两个孩子结点，这样的树就称为二叉树。孩子结点与父亲结点之间的连接像极了树的分叉，因此叫做二叉树。二叉树的结点如果有孩子结点的话，使用左结点和右结点来区分。类似可以定义多叉树：如果一棵树任意结点最多含有的结点数为 N，这棵树就是 N 叉树。

树的简介 - 图1

一个结点、空结点、单链表也是二叉树，因为它们都符合二叉树的定义；
一般而言，二叉树的两个孩子结点会规定次序，如果两个都有的话，分为左孩子和右孩子。如果只有一个孩子结点，可以只有左孩子结点，也可以只有右孩子结点。

这里有两个比较容易混淆的概念，在中西方的名称上会有一些不同，理解它们依然是从形状上理解。

完全二叉树与满二叉树

树的简介 - 图2

完全二叉树：从形态上看完全二叉树是个 只缺了最后一行右边 的的三角形。即：完全二叉树所有的结点按照从上到下、从左到右紧凑摆放，中间不会有缺失结点。我们在之前学习过的堆，就是完全二叉树的样子。

每层结点个数都是满的

满二叉树：满二叉树首先是完全二叉树。其次，从形态上看，满二叉树是一个没有缺角的三角形，即每一层结点的个数都达到了这一层能达到的最大结点数。

这里特别注意：这是中文教材对满二叉树的定义，而一些国外教材定义的满二叉树仅仅只是指代每个结点恰好有 0 或 2 个子结点。「力扣」第 894 题（所有可能的满二叉树) 中就可以看到这样的描述。在我们的语境中，「没有缺角的三角形」使用得更多。

大家不用特别纠结这些区别，就像是我们生活中总会遇到同名的人，注意从形态或者其它特征上（其它教程的上下文）区别它们就好。

二叉树的遍历

由于树形结构不是线性结构，我们观察二叉树的角度就不像线性结构那么简单、机械。

树的遍历是指：通过 一定的顺序 访问二叉树的所有结点。树的遍历有 深度优先遍历（Depth First Search）和 广度优先遍历（Breadth First Search），其中深度优先遍历又分为前序遍历、中序遍历、后序遍历。

树的简介 - 图4

友情提示：这里 Search 本意为「搜索」，因此「深度优先遍历」应该称为「深度优先搜索」，「广度优先遍历」应该称为「广度优先搜索」。但是我们认为「遍历」是这两种算法思想更形象的表述，搜索是目的，因此在后文的描述中，我们都使用「遍历」这个词。

深度优先遍历与广度优先遍历，在树的问题、图的问题中经常使用，它们的思想是非常朴素且深刻的，请大家一定要细心体会、熟练掌握。使用这两种遍历思想可以用于解决「力扣」上很多树和图的问题。

深度优先遍历

深度优先遍历的直观感受

深度优先遍历是一个比较激进的方案，前方有路就一直向前走，不走进「死胡同」里，就不会回头。我们常说的「不撞南墙不回头」就是深度优先遍历的思想。

对于二叉树来说，深度优先遍历当遍历到一个新结点的时候，先遍历当前结点，然后遍历当前结点的左子树，最后遍历当前结点的右子树。遍历子树的逻辑是递归进行下去的。

请大家仔细观察下面的动画理解深度优先遍历的思想和行为。
树的简介 - 图5

注意：深度优先遍历的方式在树形结构上有典型的「回头」的过程。

深度优先遍历需要借助「栈」实现
对于深度优先遍历而言，后遍历到的结点先输出，符合 后进先出 的规律，因此可以借助「栈」实现。下面的动画模拟了整个过程。
树的简介 - 图6

说明：

统一的逻辑是：首先将根结点入栈，然后将结点出栈，每一个出栈结点做如下操作：
- 如果出栈结点有右结点，把右结点加入栈顶；
- 如果出栈结点有左结点，把左结点加入栈顶；
直到没有结点可以入栈，依次将结点从栈顶出栈，每次出栈遵守上面的规则，只要有孩子结点，就依次入栈。出栈结点的顺序是深度优先遍历的顺序。
由于我们人为规定先遍历左子树的所有结点，再遍历右子树的所有结点。因此左、右结点的入栈顺序是：先右结点再左结点。

广度优先遍历

广度优先遍历的直观感受

广度优先遍历很像水波纹、声波的扩散。广度优先遍历是一个比较保守的方案：每条路都会试一试，并且是 齐头并进 的。我们常说的「鸡蛋不要放在同一个篮子里」，就是广度优先遍历的思想。
树的简介 - 图7

由于广度优先遍历在树形结构上 按照层次顺序，即：从根结点向下逐层进行遍历，并且同一层结点的遍历顺序为从左到右。因此，在树形结构中，广度优先遍历也叫 层序遍历。

树的简介 - 图8

广度优先遍历需要借助「队列」实现

对于广度优先遍历而言，先遍历到的结点先输出，符合 先进先出 的规律，因此可以借助「队列」实现。下面的动画模拟了整个过程。
树的简介 - 图9

说明：

统一的逻辑是：首先将根结点加入队列，然后将结点出队尾，每一个出队结点做如下操作：
- 如果出队结点有左结点，把左结点加入队尾；
- 如果出队结点有右结点，把右结点加入队尾；
直到没有结点可入队，依次将结点从队首出队，每次出队遵守上面的规则，只要有孩子结点，就依次入队。出队结点的顺序是广度优先遍历的顺序。

例 1：「力扣」第 102 题：二叉树的层序遍历

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。（即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3, 9, 20, null, null, 15, 7]，

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
  const ret = [];
  if (!root) {
    return ret;
  }
  const q = [];
  q.push(root);    // 把整个数组push进去 [[...root]]
  while (q.length !== 0) {
    const currentLevelSize = q.length;
    // 新的层级
    ret.push([]);
    for (let i = 1; i <= currentLevelSize; ++i) {
      const node = q.shift();    // 出队
      ret[ret.length - 1].push(node.val);
      if (node.left) {
        q.push(node.left);
      }
      if (node.right) {
        q.push(node.right);
      }
    }
  }
  return ret;
};

复杂度分析：

时间复杂度：O(N)，这里 N 是二叉树结点的个数，每个结点都访问一次，因此时间复杂度是 O(N)；
空间复杂度：O(N)。

「深度优先遍历」与「广度优先遍历」的比较

「深度优先遍历」与「广度优先遍历」在算法的世界里发挥了巨大的作用：

深度优先遍历和广度优先遍历都需要借助相应的数据结构，对即将访问到的元素在适当的时机缓存：深度优先遍历使用的是栈，广度优先遍历使用的是队列；
遍历可以用于搜索，找到所有需要的元素；
深度优先遍历由于其本身的特性，在面对巨大的结果集的时候，能够使用较少的性能消耗，它的另一个名字叫 回溯算法 ，我们会在下一章节向大家介绍；
基于「两点之间，线段最短」，广度优先遍历可以用于搜索无向图的最短路径，这一点是非常关键的。

练习

完成「力扣」第 107 题：二叉树的层次遍历 II（简单）；
完成《剑指 Offer》第 32 - I 题：从上到下打印二叉树（中等）；
完成《剑指 Offer》第 32 - III 题：从上到下打印二叉树 III（中等）；
完成「力扣」第 103 题：二叉树的锯齿形层次遍历（中等）。

总结

这一节我们主要介绍了：树是生活中事物之间关系的抽象，是普遍存在的事物之间的关系。树的两个遍历（深度优先遍历与广度优先遍历）的思想也是重点内容，「力扣」上很多问题都会使用这两种遍历思想完成。关于树的问题有很多，是非常重要的知识点，需要引起大家的重视。

我们在这一节只介绍了广度优先遍历，树的深度优先遍历还可以具体分为三种遍历，我们将会在下一节向大家介绍。感谢大家。

树的简介

二叉树