二叉树的层序遍历解法与优化

"二叉树的层序遍历方法及Java实现" 二叉树的后序遍历是一种遍历或搜索二叉树的算法，它按照左子树-右子树-根节点的顺序访问每个节点。然而，给定的描述和标签提及的是“二叉树的层序遍历”，而非后序遍历。层序遍历是一种广度优先搜索（BFS）的应用，它按照树的层级从上至下、从左至右访问节点。 层序遍历的核心思想是利用队列数据结构来实现。对于给定的输入，例如`root=[3,9,20,null,null,15,7]`，输出应该是`[[3],[9,20],[15,7]]`，表示每一层的节点值分别被存储在一个列表中。 **题解分析：** 1. 首先，根节点入队。 2. 当队列非空时，进行以下操作： - 计算当前队列的长度`si`，这代表当前层的节点数量。 - 依次处理`si`个队列中的节点，将其子节点（如果有）加入队列。每次处理完一个节点后，其左右子节点（如果有）都按顺序入队。 - 在每一轮迭代中，处理的节点是同一层的，它们的顺序保持从左到右。 **优化空间开销：** 为了减少哈希映射的使用，我们可以仅使用一个变量来表示状态。在上述实现中，状态可以简化为单个节点`node`，并利用队列的特性来维护层级信息。 **区别于普通广度优先搜索：** - 普通的BFS每次从队列中取出一个节点，而层序遍历在一次迭代中取出整个层的所有节点。 - 在第`i`次迭代时，队列中的元素是第`i`层的节点，且按照从左到右的顺序排列。这个性质在每次迭代后都能保持，因为新的节点总是由前一层的节点添加，且队列遵循先进先出（FIFO）原则。 **Java实现代码片段：** ```java class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> ret = new ArrayList<List<Integer>>(); if (root == null) { return ret; } Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> levelNodes = new ArrayList<>(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); levelNodes.add(node.val); if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } ret.add(levelNodes); } return ret; } } ``` 在这个Java实现中，我们创建了一个`LinkedList`作为队列，初始时将根节点入队。在循环中，我们首先计算当前队列的大小`size`，然后处理`size`个节点，将它们的值添加到当前层的列表`levelNodes`中，再将它们的子节点（如果有的话）入队。这个过程会持续到队列变空，最后返回包含所有层节点值的列表`ret`。