给定一个二叉树的根节点
{1,2,3,#,#,4,5}[[1],[2,3],[4,5]]
{8,6,10,5,7,9,11}[[8],[6,10],[5,7,9,11]]
{1,2,3,4,5}[[1],[2,3],[4,5]]
{}[]
/*
* 队列LinkedList完成层序遍历，用end记录每层结点数目
*/
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if(pRoot == null){
return result;
}
Queue<TreeNode> layer = new LinkedList<TreeNode>();
ArrayList<Integer> layerList = new ArrayList<Integer>();
layer.add(pRoot);
int start = 0, end = 1;
while(!layer.isEmpty()){
TreeNode cur = layer.remove();
layerList.add(cur.val);
start++;
if(cur.left!=null){
layer.add(cur.left);
}
if(cur.right!=null){
layer.add(cur.right);
}
if(start == end){
end = layer.size();
start = 0;
result.add(layerList);
layerList = new ArrayList<Integer>();
}
}
return result;
}
}
package Tree;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
/**
* 从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
* 思路：
* 按层次输出二叉树
* 访问根节点，并将根节点入队。
* 当队列不空的时候，重复以下操作。
* 1、弹出一个元素。作为当前的根节点。
* 2、如果根节点有左孩子，访问左孩子，并将左孩子入队。
* 3、如果根节点有右孩子，访问右孩子，并将右孩子入队。
*/
public class Solution8 {
public static void main(String[] args) {
int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
Solution8 solution8 = new Solution8();
TreeNode treeNode = solution8.createBinaryTreeByArray(array, 0);
for (ArrayList list :
solution8.Print(treeNode)) {
System.out.println(list);
}
}
/**
* 层次遍历
*
* [@param pRoot 根节点
* @return](/profile/547241) arrayLists
*/
ArrayList> Print(TreeNode pRoot) {
//存放结果
ArrayList> arrayLists = new ArrayList();
if (pRoot == null) {
return arrayLists;
}
//使用队列，先进先出
Queue queue = new LinkedList();
//存放每行的列表
ArrayList arrayList = new ArrayList();
//记录本层打印了多少个
int start = 0;
//记录下层打几个
int end = 1;
queue.add(pRoot);
while (!queue.isEmpty()) {
TreeNode temp = queue.remove();
//添加到本行的arrayList
arrayList.add(temp.val);
start++;
//每打印一个节点，就把此节点的下一层的左右节点加入队列，并记录下一层要打印的个数
if (temp.left != null) {
queue.add(temp.left);
}
if (temp.right != null) {
queue.add(temp.right);
}
//判断本层打印是否完成
if (start == end) {
//此时的queue中存储的都是下一层的节点，则end即为queue大小
end = queue.size();
start = 0;
//把arrayList添加到结果列表arrayLists中
arrayLists.add(arrayList);
//重置arrayList
arrayList = new ArrayList();
}
}
return arrayLists;
}
private TreeNode createBinaryTreeByArray(int[] array, int index) {
TreeNode tn = null;
if (index < array.length) {
int value = array[index];
tn = new TreeNode(value);
tn.left = createBinaryTreeByArray(array, 2 * index + 1);
tn.right = createBinaryTreeByArray(array, 2 * index + 2);
return tn;
}
return tn;
}
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
}
//两个队列交错打印
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int>> ret;
if(pRoot==NULL) return ret;
queue<TreeNode*> q1;
queue<TreeNode*> q2;
q1.push(pRoot);
while(!q1.empty()||!q2.empty()){
vector<int> v1;
vector<int> v2;
while(!q1.empty()){
v1.push_back(q1.front()->val);
if(q1.front()->left!=NULL) q2.push(q1.front()->left);
if(q1.front()->right!=NULL) q2.push(q1.front()->right);
q1.pop();
}
if(v1.size()!=0)
ret.push_back(v1);
while(!q2.empty()){
v2.push_back(q2.front()->val);
if(q2.front()->left!=NULL) q1.push(q2.front()->left);
if(q2.front()->right!=NULL) q1.push(q2.front()->right);
q2.pop();
}
if(v2.size()!=0)
ret.push_back(v2);
}
return ret;
}
};
我的想法就酱...
/*
*按行打印二叉树
*方法1：
* 借助两个队列按层扫描
*
* 方法2：
* 其实可以用一个队列就能做，扫描完一层插入一个null
* 然后下层扫描的时候扫描到null再插一个null
*/
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot)
{
ArrayList<ArrayList<Integer>> resutltList = new ArrayList<>();
if(pRoot == null)
{
return resutltList;
}
ArrayList<TreeNode> treeQueue = new ArrayList<>();
treeQueue.add(pRoot);
treeQueue.add(null);
while(treeQueue.get(0) != null)
{//树没有扫描完
ArrayList<Integer> currentList = new ArrayList<>();
TreeNode currentNode = treeQueue.get(0);//获取队首元素
while(currentNode != null)
{
currentList.add(currentNode.val);//将当前节点进入链
if(currentNode.left != null)
{
treeQueue.add(currentNode.left);
}
if(currentNode.right != null)
{
treeQueue.add(currentNode.right);
}
treeQueue.remove(0); //队首元素出队列
currentNode = treeQueue.get(0);//继续获取队首元素
}
treeQueue.remove(0);//上一层的null出队列
treeQueue.add(null);//扫描完一层加入一个null代表当前层的结束标志
resutltList.add(currentList); //插入当前行扫描的所有元素
}
return resutltList;
}
};
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int>> res;
queue<TreeNode*> Q;
if(!pRoot) return res;
Q.push(pRoot);
while(!Q.empty()){
vector<int> tmp;
int len = Q.size();
for(int i = 0; i < len; ++i){
TreeNode* p = Q.front();
Q.pop();
if(p->left) Q.push(p->left);
if(p->right) Q.push(p->right);
tmp.push_back(p->val);
}
res.push_back(tmp);
}
return res;
}
};
import java.util.ArrayList;
import java.util.LinkedList; /*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null; public TreeNode(int val) {
this.val = val; } }
*/
//now表示当前行剩余节点个数，next表示下一行节点总数，array存放每行的节点，当now==0,表示本行全部在array中，则加入结果集
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer> > result =new ArrayList<ArrayList<Integer> >();
ArrayList<Integer> array=new ArrayList<Integer>();
LinkedList<TreeNode> list=new LinkedList<TreeNode>();
if(pRoot==null){
return result;
}
int now=1;
int next=0;
list.add(pRoot);
while(!list.isEmpty()){
TreeNode p=list.remove();
now--;
array.add(p.val);
if(p.left!=null){
list.add(p.left);
next++;
}
if(p.right!=null){
list.add(p.right);
next++;
}
if(now==0){
result.add(new ArrayList<Integer>(array));
array.clear();
now=next;
next=0;
}
}
return result;
}
} 
import java.util.*;
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> aal= new ArrayList<ArrayList<Integer>>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
TreeNode last = pRoot;
TreeNode nLast = null;
if(pRoot==null)
return aal;
queue.offer(pRoot);
ArrayList<Integer> al = new ArrayList<Integer>();
while(!queue.isEmpty()){
pRoot = queue.poll();
al.add(pRoot.val);
if(pRoot.left!=null){
queue.offer(pRoot.left);
nLast = pRoot.left;
}
if(pRoot.right!=null){
queue.offer(pRoot.right);
nLast = pRoot.right;
}
if(pRoot==last){
aal.add(al);
last= nLast;
al = new ArrayList<Integer>();
}
}
return aal;
}}
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >();
if(pRoot==null)
return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(pRoot);
int count; //记录每层有几个节点
TreeNode temp;
while(!queue.isEmpty()){
count = queue.size();
ArrayList<Integer> list = new ArrayList<>();
for(;count>0;count--){ //count==0时这一层就遍历完了
temp = queue.poll();
list.add(temp.val);
if(temp.left!=null)
queue.offer(temp.left);
if(temp.right!=null)
queue.offer(temp.right);
}
res.add(list);
}
return res;
}
}
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
/*
//参考cyc20***佬
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(pRoot);
while (!queue.isEmpty()) {
ArrayList<Integer> list = new ArrayList();
int cin = queue.size();
while (cin-- > 0) {
TreeNode node2 = queue.poll();
if (node2 == null) {
continue;
}
queue.add(node2.left);
queue.add(node2.right);
list.add(node2.val);
}
if (list.size() != 0) {
result.add(list);
}
}
return result;
}
}
''' 解法： 从头到尾遍历当前层的节点current_nodes，然后将左孩子和右孩子分别append到一个list new_nodes中 ''' class Solution: # 返回二维列表[[1,2],[4,5]] def Print(self, pRoot): # write code here if pRoot == None: return [] node_list = [[pRoot]] result = [] while node_list: current_nodes = node_list[0] # 当前层的节点 node_list = node_list[1:] new_nodes = [] # 下一层的节点，按照从左往右的顺序存储 res = [] # 当前层得到的输出 while len(current_nodes) > 0: res.append(current_nodes[0].val) if current_nodes[0].left != None: new_nodes.append(current_nodes[0].left) if current_nodes[0].right != None: new_nodes.append(current_nodes[0].right) current_nodes = current_nodes[1:] result.append(res) if new_nodes: node_list.append(new_nodes) return result
import java.util.ArrayList;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if(pRoot==null) return result;
ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
ArrayList<Integer> temp = new ArrayList<Integer>();
ArrayList<Integer> start = new ArrayList<Integer>();
start.add(pRoot.val);
result.add(start);
int low = 0;
int high = 1;
int end = high;
queue.add(pRoot);
while(low<high){
TreeNode t = queue.get(low);
if(t.left!=null){
queue.add(t.left);
temp.add(t.left.val);
high++;
}
if(t.right!=null){
queue.add(t.right);
temp.add(t.right.val);
high++;
}
low++;
if(low==end){
end = high;
if(temp.size()!=0)
result.add(temp);
temp = new ArrayList<Integer>();
}
}
return result;
}
}
做过上一道单双行顺序相反打印的题后，应该很容易就能做出这道。
思路很简单，用队列保存结点，按顺序打印即可。
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
Queue<TreeNode> queue = new LinkedList<>();
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if (pRoot != null) queue.offer(pRoot);
while (queue.size() != 0) {
ArrayList<Integer> list = new ArrayList<>();
for (int i = queue.size(); i > 0; i--) {
TreeNode tmp = queue.poll();
if (tmp == null) throw new NullPointerException(); // 没必要，但tmp报警告很不爽所以填上
if (tmp.left != null) queue.offer(tmp.left);
if (tmp.right != null) queue.offer(tmp.right);
list.add(tmp.val);
}
res.add(list);
}
return res;
}
import java.util.*;
public class Solution {
ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
if (pRoot == null) {
return new ArrayList<ArrayList<Integer>>();
}
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
LinkedList<TreeNode> list = new LinkedList<>();
LinkedList<TreeNode> helpList = new LinkedList<>();;
list.add(pRoot);
while (!list.isEmpty()) {
if(helpList.isEmpty()) {
while (!list.isEmpty()) {
helpList.add(list.poll());
}
}
// 跳出上面的循环表示list已经空了
ArrayList<Integer> tmp = new ArrayList<>();
while (!helpList.isEmpty()) {
TreeNode cur = helpList.poll();
tmp.add(cur.val);
if(cur.left != null) {
list.add(cur.left);
}
if(cur.right != null) {
list.add(cur.right);
}
}
res.add(tmp);
}
return res;
}
}
//使用队列从左到右来保存每一层的节点
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if(pRoot==null){
return result;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(pRoot);
while(queue.size()!=0){
int cur=0;
int size = queue.size();
ArrayList<Integer> list = new ArrayList<Integer>();
Iterator<TreeNode> it = queue.iterator();
while(it.hasNext()){
list.add(it.next().val);
}
result.add(new ArrayList<Integer>(list));
while(cur<size){
TreeNode node = queue.poll();
if(node.left!=null){
queue.offer(node.left);
}
if(node.right!=null){
queue.offer(node.right);
}
cur++;
}
}
return result;
}
}
class Solution: # 返回二维列表[[1,2],[4,5]] def Print(self, pRoot): # write code here result = [] if not pRoot: return result queue = [] queue.append(pRoot) while queue: cur_row =[] queue2 = queue queue =[] while queue2: cur_node = queue2.pop(0) cur_row.append(cur_node.val) if cur_node.left: queue.append(cur_node.left) if cur_node.right: queue.append(cur_node.right) result.append(cur_row) return result
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer> > list=new ArrayList<ArrayList<Integer> > ();
if(pRoot==null)return list;
ArrayList<Integer> list2=new ArrayList<Integer>();
Queue<TreeNode> queue =new LinkedList<TreeNode>();
queue.offer(pRoot);
queue.offer(null);
while(queue.size()!=1){
TreeNode node=queue.poll();
while(node!=null){
list2.add(node.val);
if(node.left!=null)queue.offer(node.left);
if(node.right!=null)queue.offer(node.right);
node=queue.poll();
}
list.add(list2);
list2=new ArrayList<Integer>();
queue.offer(null);
continue;
}
return list;
}
}
使用队列进行层次遍历，用null区分第几行。
//用递归做的
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
depth(pRoot, 1, list);
return list;
}
private void depth(TreeNode root, int depth, ArrayList<ArrayList<Integer>> list) {
if(root == null) return;
if(depth > list.size())
list.add(new ArrayList<Integer>());
list.get(depth -1).add(root.val);
depth(root.left, depth + 1, list);
depth(root.right, depth + 1, list);
}
}
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
