剑指 Offer 32 - I. 从上到下打印二叉树（Java迭代法实现）

给定二叉树: [3,9,20,null,null,15,7]

找下规律, 发现队列可以实现层次遍历, 比如根节点3先入队，再将队列的第一个节点出队，并将出队的左右子节点（不为空）入队，直到队列为空。

3是根节点，入队。队列queue：3队列不为空，队首节点3出队，出队节点3的左右节点为9， 20，将9， 20依次入队。队列queue: 9, 20，结果：3队列不为空，队首节点9出队，出队节点9的左右节点为null，不入队。队列queue: 20，结果：3， 9队列不为空，队首节点20出队，出队节点20的左右节点为15, 17，将15， 17依次入队。队列queue: 15， 17，结果：3， 9，20队列不为空，队首节点15出队，出队节点的左右节点为null，不入队。队列queue: 17，结果：3， 9， 20， 15队列不为空，队首节点17出队，出队节点的左右节点为null，不入队。队列queue: ，结果：3， 9， 20， 15， 17队列为空，输出结果

实现代码（Java）

/*** Definition for a binary tree node.* public class TreeNode {*int val;*TreeNode left;*TreeNode right;*TreeNode(int x) { val = x; }* }*/class Solution {public int[] levelOrder(TreeNode root) {if (root == null) {return new int[0];}// 声明一个动态数组用来存放结果List<Integer> list = new ArrayList<>();// 声明一个队列Queue<TreeNode> queue = new LinkedList<>();// 将根节点入队queue.add(root);while (!queue.isEmpty()) {// 将栈顶元素出栈TreeNode temp = queue.poll();list.add(temp.val);// 如果temp的左节点不为空，将左节点入队if (temp.left != null) {queue.add(temp.left);}// 如果temp的右节点不为空，将右节点入队if (temp.right != null) {queue.add(temp.right);}}// 利用Stream流实现List向int[]转换return list.stream().mapToInt(Integer::intValue).toArray();}}

构建二叉树的工具类

import java.util.ArrayList;import java.util.List;public class ConstructBinaryTree {/***根据数组构建二叉树* @param nums 二叉树的数组表示* @return 构建完成后二叉树的根节点*/public static TreeNode constructBinaryTree(int[] nums) {// 构建与数组相同大小的树节点链表List<TreeNode> treeNodeList = nums.length > 0 ? new ArrayList<>(nums.length) : null;TreeNode root = null;// 初始化链表的每一个树节点为数组元素for (int i = 0; i < nums.length; i ++) {TreeNode node = null;// 用-1表示空节点if (nums[i] != -1) {node = new TreeNode(nums[i]);}treeNodeList.add(node);if (i == 0) {root = node;}}/** 遍历树节点链表，给每一个树节点的左右孩子赋值* 结束规则是 i * 2 + 1 < nums.length* 而不是i * 2 + 2 < nums.length* 如果结束规则为 i * 2 + 2 < nums.length 时， [2,7,9,-1,1,9,6,-1,-1,10] 的 10 就会漏掉*/for (int i = 0; i * 2 + 1 < nums.length; i ++) {TreeNode node = treeNodeList.get(i);if (node != null) {// 线式存储转换为链式存储的关键node.left = treeNodeList.get(i * 2 + 1);// 再次判断一下， 不忽略如何一个节点if (i * 2 + 2 < nums.length) {node.right = treeNodeList.get(i * 2 + 2);}}}return root;}}