今日题目：
- 144. 二叉树的前序遍历
- 94. 二叉树的中序遍历
- 145. 二叉树的后序遍历
- 102. 二叉树的层序遍历
- 107. 二叉树的层序遍历 II
- 199. 二叉树的右视图
- 637. 二叉树的层平均值
- 429. N 叉树的层序遍历
- 515. 在每个树行中找最大值
- 116. 填充每个节点的下一个右侧节点指针
- 117. 填充每个节点的下一个右侧节点指针 II
- 104. 二叉树的最大深度
- 111. 二叉树的最小深度
目录
- Problem 1：二叉树的递归遍历 【easy】
- Problem 2：二叉树的迭代遍历 【classic】
- 2.1 前序遍历 迭代版
- 2.2 中序遍历 迭代版
- 2.3 后序遍历 迭代版 【必背】
- Problem 3：二叉树的层次遍历 【classic】
- LC 102. 二叉树的层序遍历
- 其他例题
今天主要学习了二叉树的递归遍历、迭代遍历和层序遍历，其中递归遍历和层序遍历都很简单，而迭代遍历的代码写起来稍有困难，这部分需要在理解的基础上，把伪代码背过。
Problem 1：二叉树的递归遍历 【easy】
递归遍历二叉树很简单了，可以拿这三个遍历题练练手：
- 144. 二叉树的前序遍历
- 94. 二叉树的中序遍历
- 145. 二叉树的后序遍历
Problem 2：二叉树的迭代遍历 【classic】
2.1 前序遍历 迭代版
144. 二叉树的前序遍历
伪代码思路：
void preOrder2(TreeNode T) {
Stack S;
TreeNode p = T;
while (p !=null && !S.empty()) {
if (p) {
visit(p); // 第一次经过时访问之
S.push(p);
p = p.left(); // 一路向左
} else {
S.pop(p);
p = p.right(); // 向右走（step 10）
}
}
}
Java 代码实现：
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null) {
return Collections.emptyList();
}
List<TreeNode> stack = new ArrayList<>();
List<Integer> result = new ArrayList<>();
TreeNode p = root;
while (p != null || !stack.isEmpty()) {
if (p != null) {
result.add(p.val);
stack.addLast(p);
p = p.left;
} else {
p = stack.removeLast();
p = p.right;
}
}
return result;
}
}
2.2 中序遍历 迭代版
94. 二叉树的中序遍历
伪代码如下：
void inOrder2(TreeNode T) {
Stack S;
TreeNode p = T; // p 是遍历指针
while (p != null || !S.empty()) { // 栈不空或者 p 不空时循环
// 一路向左直到空节点
if (p) {
S.push(p); // 当前节点入栈
p = p.left; // 向左走
}
// 遇到空节点
else {
S.pop(p); // 访问栈顶元素（step9），由于接下来要访问之，故 pop
visit(p); // 访问之
p = p.right; // 向右子树走（step10）
}
}
}
2.3 后序遍历 迭代版 【必背】
145. 二叉树的后序遍历
这个建议直接背过，掌握这个算法思路后，并不难背，大不了多写几遍代码。
算法思路：① 一路向左走并入栈，直到空节点；② 碰到空节点后，读取栈顶元素但不弹出（step9）：如果存在右孩子并且未访问过（为了确定之前是从左孩子返回过来的），则向右走；否则，栈顶元素出栈并访问之。
- 为了区分返回到一个节点时是从左子树回来的还是从右子树回来的，代码设定了辅助指针 recent，它指向最近访问过的节点，当 p.right != recent 时，表示这是从左子树回来的，还没有访问过右子树。
后序遍历迭代版特点：
- 当一个节点的左右子树都被访问后才能出栈（pop）。
- 实际上，当访问一个节点 p 时，栈中节点恰好是 p 节点的所有祖先，从栈底到栈顶再加上 p 节点，刚好构成从根节点到 p 节点的一条路径。很多算法设计都利用了这一思想，比如求根到某节点的路径，求两个节点的最近公共祖先等。
伪代码如下：
void postOrder2(TreeNode T) {
Stack S;
TreeNode p = T, recent = null;
while (p != null && !S.empty()) {
if (p) {
S.push(p);
p = p.left;
} else { // 向右
p = S.top(); // 读取栈顶节点
if (p.right && p.right != recent) { // 若存在右孩子，且未被访问过
p = p.right; // 向右走
} else { // 否则弹出节点并访问之
S.pop(p);
visit(p);
recent = p; // 更新最近访问的节点
p = null; // 节点访问完后，重置 p 指针
}
} // end else
} // end while
}
代码实现：
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<TreeNode> stack = new ArrayList<>();
List<Integer> result = new ArrayList<>();
TreeNode p = root, recent = null;
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.addLast(p);
p = p.left;
} else {
p = stack.getLast();
if (p.right != null && recent != p.right) {
p = p.right;
} else {
result.add(p.val);
recent = p;
stack.removeLast();
p = null;
}
}
}
return result;
}
}
Problem 3：二叉树的层次遍历 【classic】
层序遍历的模板可以解决一大类问题，需要谨记。
算法思想：
- 初始化一个辅助队列 Q；
- 根节点入队；
- 若 Q 非空，则队头节点出队并访问之，并将其左右孩子入队（如果有的话）；
- 重复 3 直至队空。
伪代码实现：
void levelOrder(TreeNode T) {
Queue Q; // 1. 初始化一个辅助队列
TreeNode p;
Q.offer(T); // 2. 根节点入队
while (!Q.empty()) { // 3. 若 Q 非空，则
int sz = Q.size(); // 这一层的节点个数
// 依次将这一层的节点出队
for (int i = 0; i < sz; i++) {
var curr = Q.poll();
visit(curr); // 访问之
// 将左右子节点加入队列
if (curr.left != null) {
Q.offer(curr.left);
}
if (curr.right != null) {
Q.offer(curr.right);
}
}
} // 4. 重复直至队空
return;
}
LC 102. 二叉树的层序遍历
102. 二叉树的层序遍历
这是经典使用层序遍历来获取二叉树的层序遍历顺序，基本与模板一致：
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return Collections.emptyList();
}
Deque<TreeNode> queue = new LinkedList<>(); // 队列
queue.addLast(root);
List<List<Integer>> result = new ArrayList<>();
while (!queue.isEmpty()) {
int sz = queue.size();
List<Integer> levelNums = new ArrayList<>();
for (int i = 0; i < sz; i++) {
var node = queue.removeFirst();
levelNums.add(node.val);
// 将左右子节点加入队列
if (node.left != null) {
queue.addLast(node.left);
}
if (node.right != null) {
queue.addLast(node.right);
}
}
result.add(levelNums);
}
return result;
}
}
其他例题
借助二叉树的层序遍历的模板，可以一口气解决下面十个题目：
- 102. 二叉树的层序遍历
- 107. 二叉树的层序遍历 II
- 199. 二叉树的右视图
- 637. 二叉树的层平均值
- 429. N 叉树的层序遍历
- 515. 在每个树行中找最大值
- 116. 填充每个节点的下一个右侧节点指针
- 117. 填充每个节点的下一个右侧节点指针 II
- 104. 二叉树的最大深度
- 111. 二叉树的最小深度
