按层打印二叉树

二叉树是一种常见的数据结构，由n（你>=0）个节点构成，每个节点最多有两个子二叉树。 由二叉树的定义可知，一棵二叉树由三部分组成：根节点、左子树和右子树。二叉树的遍历方式有先序遍历、中序遍历和后序遍历。 先序遍历：首先访问根节点，然后访问根节点左孩子，再访问根节点的右孩子。

中序遍历：首先访问根节点左孩子，然后访问根节点，在访问根节点的右孩子。

后序遍历：首先访问根节点左孩子，然后访问根节点的右孩子，再访问根节点。

上述三种遍历方式原理相同，可以采用递归的方式实现遍历。

这里要说的是二叉树的另一种遍历方法：按层遍历。

按层遍历即从二叉树的根节点开始从上至下从左至右依次访问节点。 在介绍按层遍历的实现前先定义一下二叉树的结构。

class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } }

上述代码即定义了二叉树中每个节点的结构。节点的数据 val、该节点的左孩子 left和该节点的有孩子right。

下面以一个实例问题实现二叉树的按层遍历。 按层遍历算法如下： 1、初始化设置一个队列； 2、把根节点先入队列； 3、当队列非空时： ①、出队列取得当前队头结点，访问该节点； ②、若该结点的左孩子结点非空，则将该结点的左孩子结点放入队列。 ③、若该结点的右孩子结点非空，则将该结点的右孩子结点放入队列。 4、结束

问题 给定二叉树的根结点root，请返回打印结果，结果按照每一层一个数组进行储存，所有数组的顺序按照层数从上往下，且每一层的数组内元素按照从左往右排列。

---

/** * 二叉树的按层遍历 * * @param root * 二叉树的根节点 * @return 返回一个二维数组表示每一层由哪些数据构成 */ public static int[][] printTree(TreeNode root) { // 如果二叉树为空立即结束 if (root == null) { return null; } // 作用1：存储每一层的数据集合 // 作用2：转化为数组返回 ArrayList<ArrayList<Integer>> array = new ArrayList<>(); // 临时存放每层结点 ArrayList<Integer> temp; int last = 0; int nlast = 0; // 当前结点 TreeNode curr; Queue<TreeNode> queue = new LinkedList<>(); // 步骤1 ：根节点入队列 curr = root; queue.offer(curr); nlast = curr.val; last = nlast; temp = new ArrayList<>(); // 步骤二 ： 循环遍历二叉树 while (!queue.isEmpty()) { curr = queue.poll(); temp.add(curr.val); // 左孩子非空，将左孩子如队列 if (curr.left != null) { queue.offer(curr.left); nlast = curr.left.val; } // 右孩子非空，将右孩子入队列 if (curr.right != null) { queue.offer(curr.right); nlast = curr.right.val; } if (curr.val == last) { last = nlast; array.add(temp); temp = new ArrayList<>(); } } // 将array中的结点数据转换为二维数组返回 int[][] result = new int[array.size()][]; for (int i = 0; i < result.length; i++) { ArrayList<Integer> tempArray = array.get(i); result[i] = new int[tempArray.size()]; int n = result[i].length; for (int j = 0; j < n; j++) { result[i][j] = tempArray.get(j); } } return result; }