NC15 求二叉树的层序遍历

答案：二叉树的层序遍历可以通过队列实现，具体步骤如下：

初始化队列：若根节点非空，将其加入队列。
循环处理队列：
记录当前队列长度（即当前层节点数）。
遍历当前层节点，依次取出节点值并加入临时列表，同时将其左右子节点（若存在）加入队列。
将临时列表加入结果列表。
返回结果：队列为空时，返回结果列表。

代码实现（Java）import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Queue;public class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) { return result; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> level = new ArrayList<>(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } result.add(level); } return result; }}class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; }}关键点说明

队列的作用：
队列用于按层存储待访问的节点，确保先访问的节点其子节点优先被处理（FIFO特性）。
分层处理：
通过记录每层的节点数（size = queue.size()），确保内层循环仅处理当前层节点，避免跨层干扰。
时间复杂度：
O(n)，其中 n 为节点数，每个节点仅被访问一次。
空间复杂度：
O(n)，队列最多存储一层的节点（最坏情况下为完全二叉树的叶子层，约 n/2 个节点）。

示例解析

输入：{3,9,20,#,#,15,7}二叉树结构：

3 / 9 20 / 15 7

执行过程：

队列初始化为 [3]。
第一层（size=1）：
取出 3，加入 [3]，队列变为 [9, 20]。
第二层（size=2）：
取出 9，加入 [9]；取出 20，加入 [20]，队列变为 [15, 7]。
第三层（size=2）：
取出 15 和 7，分别加入 [15, 7]，队列为空。输出：[[3], [9, 20], [15, 7]]

其他语言实现思路

Python：使用 collections.deque 替代队列，逻辑与Java一致。
C++：使用 std::queue，需注意动态数组（如 vector）的初始化。

通过队列的分层处理，可高效实现二叉树的层序遍历。

您可能感兴趣问答

Collapsible

热门标签

热点问答