【LeetCode】升级打怪之路 Day 14：二叉树的遍历

今日题目：

• 144. 二叉树的前序遍历
• 94. 二叉树的中序遍历
• 145. 二叉树的后序遍历
• 102. 二叉树的层序遍历
• 107. 二叉树的层序遍历 II
• 199. 二叉树的右视图
• 637. 二叉树的层平均值
• 429. N 叉树的层序遍历
• 515. 在每个树行中找最大值
• 116. 填充每个节点的下一个右侧节点指针
• 117. 填充每个节点的下一个右侧节点指针 II
• 104. 二叉树的最大深度
• 111. 二叉树的最小深度

今天主要学习了二叉树的递归遍历、迭代遍历和层序遍历，其中递归遍历和层序遍历都很简单，而迭代遍历的代码写起来稍有困难，这部分需要在理解的基础上，把伪代码背过。

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），由于接下来要访问之，故 popvisit(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】

层序遍历的模板可以解决一大类问题，需要谨记。

算法思想：

1. 初始化一个辅助队列 Q；
2. 根节点入队；
3. 若 Q 非空，则队头节点出队并访问之，并将其左右孩子入队（如果有的话）；
4. 重复 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. 二叉树的最小深度