算法—按层打印二叉树（一层一行）

本文主要是介绍算法—按层打印二叉树（一层一行），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

方法一

用层序遍历+记录每层的节点数

1. 层序遍历的思想，引入队列，不断将节点的左右孩子入队出队；
2. 引入两个参数：start和end，list每添加一个节点，start都要加一，end为当前层的节点数，初始值为1，后面为队列的尺寸；
3. 当start=end时，同一层的元素已经全部被添加到list中了，此时要将该list添加到listAll里面，并初始化start，end和list；

代码

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;public class Solution {ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {//方法1：层序遍历+引入一个start和end记录当前层ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>();//装所有层的节点if(pRoot == null){return listAll;}ArrayList<Integer> list = new ArrayList<>();  //装同一层的节点Queue<TreeNode> queue = new LinkedList<TreeNode>(); //引入队列queue.add(pRoot);//将根节点入队int start = 0;int end = 1;while(!queue.isEmpty()){TreeNode node = queue.remove();  //队首元素出队list.add(node.val);  //将当前节点加入liststart++;if(node.left != null){queue.add(node.left);}if(node.right != null){queue.add(node.right);}if(start == end){  //同一层的元素都加到list里面了listAll.add(new ArrayList<Integer>(list));end = queue.size();   //设置end为当前队列大小start = 0; //初始化start为0list = new ArrayList<Integer>(); //初始化list}}return listAll;}
}

方法二

利用一个方法depth（），将当前节点node，当前节点所处深度depth，当前的listAll作为参数传进去，判断如果depth>listAll.size()，说明需要新增加一层的空间，并将该节点add入这层，然后递归。

代码

import java.util.ArrayList;public class Solution {ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {//方法2：把当前节点所处深度depth和当前的listAll作为参数往下传，递归实现ArrayList<ArrayList<Integer>> listAll = new ArrayList<>();//记录所有层节点depth(pRoot, 1, listAll); //1为当前节点深度return listAll;}public void depth(TreeNode node, int depth, ArrayList<ArrayList<Integer>> listAll){if(node == null){return;}if(depth > listAll.size()){ //当前节点的深度大于listAll里面装的层数listAll.add(new ArrayList<>()); //listAll里添加一层的空间}listAll.get(depth-1).add(node.val); //将node.val加入当前层//递归depth(node.left, depth+1, listAll);depth(node.right, depth+1, listAll);}
}

这篇关于算法—按层打印二叉树（一层一行）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---