递归遍历（DFS）
二叉树的遍历框架：
// 基本的二叉树节点
class TreeNode {
int val;
TreeNode left, right;
}
// 二叉树的遍历框架
void traverse(TreeNode root) {
if (root == null) {
return;
}
traverse(root.left);
traverse(root.right);
}
这段短小精干的代码为什么能遍历二叉树？又是以什么顺序遍历二叉树的？请看VCR
traverse 函数的遍历顺序就是一直往左子节点走，直到遇到空指针不能再走了，才尝试往右子节点走一步；然后再一直尝试往左子节点走，如此循环；如果左右子树都走完了，则返回上一层父节点。其实看代码也能看出来，先递归调用的 root.left，然后才递归调用的 root.right 嘛。
这个递归遍历节点顺序是固定的，务必记住这个顺序，否则你肯定玩不转二叉树结构。
那么有一些数据结构基础的读者肯定要问了：不对呀，只要上过大学的数据结构课程都知道，二叉树有前/中/后序三种遍历，会得到三种不同顺序的结果。为啥你这里说递归遍历节点的顺序是固定的呢？
这个问题很好，我来解答一下。
Important
递归遍历的顺序，即 traverse 函数访问节点的顺序确实是固定的。正如上面那个视频，root 指针在树上移动的顺序是固定的。
但是你在 traverse 函数中不同位置写代码，效果是可以不一样的。前中后序遍历的结果不同，原因是因为你把代码写在了不同位置，所以产生了不同的效果。
比方说，刚进入一个节点的时候，你还对它的子节点一无所知，而当你要离开一个节点的时候，它的所有子节点你都遍历过了。那么在这两种情况下写的代码，肯定是可以有不同的效果的。
你所谓的前中后序遍历，其实就是在上述二叉树遍历框架的不同位置写代码：
// 二叉树的遍历框架
void traverse(TreeNode root) {
if (root == null) {
return;
}
// 前序位置
traverse(root.left);
// 中序位置
traverse(root.right);
// 后序位置
}
前序位置的代码会在进入节点时执行；中序位置的代码会在左子树遍历完成后，遍历右子树之前执行；后序位置的代码会在左右子树遍历完成后执行：
层序遍历（BFS）
上面的递归遍历是依赖函数堆栈递归遍历二叉树的，如果把递归函数 traverse 看做一个指针，那么这个指针在二叉树上游走的顺序大概是从最左侧开始，一列一列走到最右侧。
二叉树的层序遍历，顾名思义，就是一层一层地遍历二叉树。这个遍历方式需要借助队列来实现，而且根据不同的需求，主要有三种不同的写法，下面一一列举。
写法一
这是最简单的写法，代码如下：
void levelOrderTraverse(TreeNode root) {
if (root == null) {
return;
}
Queue q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
TreeNode cur = q.poll();
// 访问 cur 节点
System.out.println(cur.val);
// 把 cur 的左右子节点加入队列
if (cur.left != null) {
q.offer(cur.left);
}
if (cur.right != null) {
q.offer(cur.right);
}
}
}
cur 变量在树上游走的顺序可以得到层序遍历是一层一层，从左到右的遍历二叉树节点
这种写法的优缺点
这种写法最大的优势就是简单。每次把队头元素拿出来，然后把它的左右子节点加入队列，就完事了。但是这种写法的缺点是，无法知道当前节点在第几层。知道节点的层数是个常见的需求，比方说让你收集每一层的节点，或者计算二叉树的最小深度等等。
所以这种写法虽然简单，但用的不多，下面介绍的写法会更常见一些。
写法二
对上面的解法稍加改造，就得出了下面这种写法：
void levelOrderTraverse(TreeNode root) {
if (root == null) {
return;
}
Queue q = new LinkedList<>();
q.offer(root);
// 记录当前遍历到的层数（根节点视为第 1 层）
int depth = 1;
while (!q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
// 访问 cur 节点，同时知道它所在的层数
System.out.println("depth = " + depth + ", val = " + cur.val);
// 把 cur 的左右子节点加入队列
if (cur.left != null) {
q.offer(cur.left);
}
if (cur.right != null) {
q.offer(cur.right);
}
}
depth++;
}
}
注意代码中的内层 for 循环：
int sz = q.size();
for (int i = 0; i < sz; i++) {
...
}
这个变量 i 记录的是节点 cur 是当前层的第几个，大部分算法题中都不会用到这个变量，所以你完全可以改用下面的写法：
int sz = q.size();
while (sz-- > 0) {
...
}
这个属于细节问题，按照自己的喜好来就行。
但是注意队列的长度 sz 一定要在循环开始前保存下来，因为在循环过程中队列的长度是会变化的，不能直接用 q.size() 作为循环条件。
写法三
既然写法二是最常见的，为啥还有个写法三呢？因为要给后面的进阶内容做铺垫。
现在我们只是在探讨二叉树的层序遍历，但是二叉树的层序遍历可以衍生出 多叉树的层序遍历，图的 BFS 遍历，以及经典的 BFS 暴力穷举算法框架，所以这里要拓展延伸一下。
回顾写法二，我们每向下遍历一层，就给 depth 加 1，可以理解为每条树枝的权重是 1，二叉树中每个节点的深度，其实就是从根节点到这个节点的路径权重和，且同一层的所有节点，路径权重和都是相同的。
那么假设，如果每条树枝的权重和可以是任意值，现在让你层序遍历整棵树，打印每个节点的路径权重和，你会怎么做？这样的话，同一层节点的路径权重和就不一定相同了，写法二这样只维护一个 depth 变量就无法满足需求了。
写法三就是为了解决这个问题，在写法一的基础上添加一个 State 类，让每个节点自己负责维护自己的路径权重和，代码如下：
class State {
TreeNode node;
int depth;
State(TreeNode node, int depth) {
this.node = node;
this.depth = depth;
}
}
void levelOrderTraverse(TreeNode root) {
if (root == null) {
return;
}
Queue q = new LinkedList<>();
// 根节点的路径权重和是 1
q.offer(new State(root, 1));
while (!q.isEmpty()) {
State cur = q.poll();
// 访问 cur 节点，同时知道它的路径权重和
System.out.println("depth = " + cur.depth + ", val = " + cur.node.val);
// 把 cur 的左右子节点加入队列
if (cur.node.left != null) {
q.offer(new State(cur.node.left, cur.depth + 1));
}
if (cur.node.right != null) {
q.offer(new State(cur.node.right, cur.depth + 1));
}
}
}
这样每个节点都有了自己的 depth 变量，是最灵活的，可以满足所有 BFS 算法的需求。但是由于要额外定义一个 State 类比较麻烦，所以非必要的话，用写法二就够了。
为什么 BFS 常用来寻找最短路径
来看力扣第 111 题「二叉树的最小深度」：
- 二叉树的最小深度 | 力扣 | LeetCode |
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
提示：
● 树中节点数的范围在 [0, 105] 内
● -1000 <= Node.val <= 1000
二叉树的最小深度即「根节点到最近的叶子节点的距离」，所以这道题本质上就是让你求最短距离。
DFS 递归遍历和 BFS 层序遍历都可以解决这道题，先看 DFS 递归遍历的解法：
class Solution {
// 记录最小深度（根节点到最近的叶子节点的距离）
private int minDepth = Integer.MAX_VALUE;
// 记录当前遍历到的节点深度
private int currentDepth = 0;
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
// 从根节点开始 DFS 遍历
traverse(root);
return minDepth;
}
private void traverse(TreeNode root) {
if (root == null) {
return;
}
// 前序位置进入节点时增加当前深度
currentDepth++;
// 如果当前节点是叶子节点，更新最小深度
if (root.left == null && root.right == null) {
minDepth = Math.min(minDepth, currentDepth);
}
traverse(root.left);
traverse(root.right);
// 后序位置离开节点时减少当前深度
currentDepth--;
}
}
每当遍历到一条树枝的叶子节点，就会更新最小深度，当遍历完整棵树后，就能算出整棵树的最小深度。你能不能在不遍历完整棵树的情况下，提前结束算法？不可以，因为你必须确切的知道每条树枝的深度（根节点到叶子节点的距离），才能找到最小的那个。
下面来看 BFS 层序遍历的解法。按照 BFS 从上到下逐层遍历二叉树的特点，当遍历到第一个叶子节点时，就能得到最小深度：
class Solution {
public int minDepth(TreeNode root) {
if (root == null) return 0;
Queue q = new LinkedList<>();
q.offer(root);
// root 本身就是一层，depth 初始化为 1
int depth = 1;
while (!q.isEmpty()) {
int sz = q.size();
// 遍历当前层的节点
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
// 判断是否到达叶子结点
if (cur.left == null && cur.right == null)
return depth;
// 将下一层节点加入队列
if (cur.left != null)
q.offer(cur.left);
if (cur.right != null)
q.offer(cur.right);
}
// 这里增加步数
depth++;
}
return depth;
}
}
由于 BFS 逐层遍历的逻辑，第一次遇到目标节点时，所经过的路径就是最短路径，算法可能并不需要遍历完所有节点就能提前结束。DFS 遍历当然也可以用来寻找最短路径，但必须遍历完所有节点才能得到最短路径。从时间复杂度的角度来看，两种算法在最坏情况下都会遍历所有节点，时间复杂度都是 O(N)O(N)，但在一般情况下，显然 BFS 算法的实际效率会更高。所以在寻找最短路径的问题中，BFS 算法是首选。
为什么 DFS 常用来寻找所有路径
在寻找所有路径的问题中，你会发现 DFS 算法用的比较多，BFS 算法似乎用的不多。
理论上两种遍历算法都是可以的，只不过 BFS 算法寻找所有路径的代码比较复杂，DFS 算法代码比较简洁。你想啊，就以二叉树为例，如果要用 BFS 算法来寻找所有路径（根节点到每个叶子节点都是一条路径），队列里面就不能只放节点了，而需要使用第三种写法，新建一个 State 类，把当前节点以及到达当前节点的路径都存进去，这样才能正确维护每个节点的路径，最终计算出所有路径。
而使用 DFS 算法就简单了，它本就是一条树枝一条树枝从左往右遍历的，每条树枝就是一条路径，所以 DFS 算法天然适合寻找所有路径。最后结合代码和可视化面板讲解一下，先看 DFS 算法的可视化面板，你可以多次点击 if (root === null) 这部分代码，观察 DFS 算法遍历所有节点并收集根节点到叶子节点的所有路径：
综上，DFS 算法在寻找所有路径的问题中更常用，而 BFS 算法在寻找最短路径的问题中更常用。
