递归遍历（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() 作为循环条件。
