给定二叉树: [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;}}