1. 题目
剑指 Offer 32 - I. 从上到下打印二叉树
2. 描述
从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回:
[3,9,20,15,7]
3. 实现方法
3.1 方法 1
3.1.1 思路
判断根节点是否为 null,是则直接输出 []
然后用一个列表 list 用于存放二叉树层序遍历结果,同时用一个队列 queue 来存放二叉树层序遍历的节点;
只要队列 queue 不为空,则每次将队尾元素出队并存入 list
然后对左右子节点进入入队处理
最后将列表 list 转换为数组返回即可
主要进行出入队操作,时间复杂度为 O ( n ) O(n)O(n),然后还有将列表转换为数组,时间复杂度为 O ( n ) O(n)O(n),所以最终时间复杂度仍为 O ( n ) O(n)O(n);
3.1.2 实现
public int[] levelOrder(TreeNode root) { // 队列为空,输出 [] if (root == null) { return new int[0]; } // 列表用于存放最终结果 ArrayList<Integer> list = new ArrayList<>(); // 队列用于存放树的顺序遍历 Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { // 根节点出队,并将其加入列表 TreeNode node = queue.poll(); list.add(node.val); // 处理左子节点 if (node.left != null) { queue.add(node.left); } // 处理右子节点 if (node.right != null) { queue.add(node.right); } } // 将列表转换为数组 int[] res = new int[list.size()]; for (int i = 0; i < list.size(); i++) { res[i] = list.get(i); } return res; }