算法通关村第五关-二叉树遍历（层数优先）之经典问题：简单的层序遍历、层序遍历分层、自底向上的层序遍历

基础知识（青铜挑战）

• 了解二叉树的基础知识

实战训练（白银挑战）

简单的层序遍历

• 基本的层序遍历思路很清晰：

  • 给你一个二叉树根节点，你需要创建一个队列 queue 来遍历节点，一个链表 list 来存储节点的数据域，即值

  • 首先将根节点入队

  • 队列 queue 出队，将该节点值存入 list，再依次将左右孩子节点入队

  • 重复以上操作，每个节点出对后，都存储该节点值到 list 中，再依次将左右孩子节点入队，直到队列 queue为空

  • 这样得到的数据链表 list 就是按层序遍历的顺序得到的

• 具体代码如下：（2023/09/09午）

public static List<Integer> simpleLevelOrder(TreeNode root) {if (root == null) {return new ArrayList<Integer>();}
​List<Integer> res = new ArrayList<Integer>();LinkedList<TreeNode> queue = new LinkedList<TreeNode>();//将根节点放入队列中，然后不断遍历队列queue.add(root);//有多少元素执行多少次while (queue.size() > 0) {//获取当前队列的长度，这个长度相当于 当前这一层的节点个数TreeNode t = queue.remove();res.add(t.val);if (t.left != null) {queue.add(t.left);}if (t.right != null) {queue.add(t.right);}}return res;}

层序遍历分层

• 层序遍历我们做到了，这里添加一个要求：对层序遍历的节点值分层处理，即二叉树每层的节点值分别存放进一个链表 list 中

• 这个代码怎么写呢？很简单的，按这个思路走：

  • 我们之前层序遍历时，每出队一个节点，都把其值存入 list 链表中，然后入队其孩子节点

  • 在开始出队某一层的节点时，此时队列的节点数，就是二叉树这一层的节点数

  • 那我们根据可以某时刻队列容量来遍历队列，将这层的节点全部出队，并且把节点值存入该层独有的 list 中

  • 当然了，每个节点出队后，要将自己的孩子节点依次入队

  • 这样，当队列为空时，我们得到了各层的节点链表 list，返回一个包含各层 list 的 list 即可

• 具体代码如下：（2023/09/09晚）

  public static List<List<Integer>> level102Order(TreeNode root) {if (root == null) {return new ArrayList<List<Integer>>();}
​List<List<Integer>> res = new ArrayList<List<Integer>>();LinkedList<TreeNode> queue = new LinkedList<TreeNode>();//将根节点放入队列中，然后不断遍历队列queue.add(root);while (queue.size() > 0) {//获取当前队列的长度，这个长度相当于 当前这一层的节点个数int size = queue.size();ArrayList<Integer> tmp = new ArrayList<Integer>();//将队列中的元素都拿出来(也就是获取这一层的节点)，放到临时list中//如果节点的左/右子树不为空，也放入队列中for (int i = 0; i < size; ++i) {TreeNode t = queue.remove();tmp.add(t.val);if (t.left != null) {queue.add(t.left);}if (t.right != null) {queue.add(t.right);}}//将临时list加入最终返回结果中res.add(tmp);}return res;}

自底向上的层序遍历

• 在前面学习的基础上，实现这个要求就很简单了

• 在拿到各层节点值的 list 后，按头插的方式，插入链表 list 中，就实现了自底向上的层序遍历了（2023/09/09晚）

• 具体代码如下：

public static List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> levelOrder = new LinkedList<List<Integer>>();if (root == null) {return levelOrder;}Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);while (!queue.isEmpty()) {List<Integer> level = new ArrayList<Integer>();int size = queue.size();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();level.add(node.val);TreeNode left = node.left, right = node.right;if (left != null) {queue.offer(left);}if (right != null) {queue.offer(right);}}levelOrder.add(0, level);//栈}return levelOrder;}