首页 > 试题广场 >

把二叉树打印成多行

[编程题]把二叉树打印成多行

热度指数：352356 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个节点数为 n 二叉树，要求从上到下按层打印二叉树的 val 值，同一层结点从左至右输出，每一层输出一行，将输出的结果存放到一个二维数组中返回。

例如：
给定的二叉树是{1,2,3,#,#,4,5}

该二叉树多行打印层序遍历的结果是

[

[1],

[2,3],

[4,5]

]

数据范围：二叉树的节点数 $0 \le n \le 1000$ ， $0 \le val \le 1000$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

输入描述:

给定一个二叉树的根节点

示例1

输入

{1,2,3,#,#,4,5}

输出

[[1],[2,3],[4,5]]

示例2

输入

{8,6,10,5,7,9,11}

输出

[[8],[6,10],[5,7,9,11]]

示例3

输入

{1,2,3,4,5}

输出

[[1],[2,3],[4,5]]

示例4

输入

{}

输出

[]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Java

牛客839384289号

public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) {
    // write code here
    ArrayList<ArrayList<Integer>> res=new ArrayList<>();
    if(pRoot==null){
        return res;
    }
    LinkedList<TreeNode> queue=new LinkedList<>();
    queue.add(pRoot);
    while(!queue.isEmpty()){
        int len=queue.size();
        ArrayList<Integer> list=new ArrayList<>();
        for(int i=0;i<len;i++){
            TreeNode node=queue.poll();
            if(node.left!=null){
                queue.add(node.left);
            }
            if(node.right!=null){
                queue.add(node.right);
            }
            list.add(node.val);
        }
        res.add(list);
    }
    return res;
}

编辑于 2024-03-10 15:50:17 回复(0)

Java

梁山教父

import java.util.*;


/*
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>> allList = new ArrayList<>();
        if (pRoot == null) {
            return allList;
        }
        //队列，保存当层的节点
        Queue<TreeNode> queue = new ArrayDeque<>();
        //添加根节点
        queue.add(pRoot);
        while (!queue.isEmpty()) {
            //保存当前层的节点的值
            ArrayList<Integer> tmp = new ArrayList<>();
            int size = queue.size();
            //如果有儿子就添加进去，没有就不添加到队列
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                //将当层节点值添加到集合
                tmp.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            allList.add(tmp);
        }
        return allList;
    }

}

发表于 2023-05-05 18:58:30 回复(0)

Java

T丶KOATH

import java.util.*;
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> > res = new ArrayList<>();
if(pRoot == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.add(pRoot);
int count = q.size();
TreeNode tmp = null;
while(!q.isEmpty()){
ArrayList<Integer> s = new ArrayList<>();
count = q.size();
for(int i =0 ; i<count ; i++){
tmp = q.poll();
s.add(tmp.val);
if(tmp.left!=null)q.add(tmp.left);
if(tmp.right!=null)q.add(tmp.right);
}
res.add(s);
}
return res;

}

}

发表于 2022-09-01 16:01:42 回复(0)

Java

勇敢牛牛不怕难

import java.util.*;
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>> res = new ArrayList<>();
        if(pRoot==null){
            return res;
        }
        Deque<TreeNode> list = new ArrayDeque<>();
        list.push(pRoot);
        while (!list.isEmpty()) {
            int size = list.size();
            ArrayList<Integer> temp = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = list.pollFirst();
                temp.add(treeNode.val);
                if (treeNode.left != null) {
                    list.addLast(treeNode.left);
                }
                if (treeNode.right != null) {
                    list.addLast(treeNode.right);
                }

            }
            res.add(temp);
        }

        return res;
    }
    
}

发表于 2022-07-01 16:49:11 回复(0)

Java

zhenggw

import java.util.*;


/*
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> > ans = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(pRoot!=null){
            queue.add(pRoot);
        }
        int sum = 1;
        while(!queue.isEmpty()){
            ArrayList<Integer> list = new ArrayList<>();
            int flag = 0;
            while(sum!=0){
                TreeNode tmp = queue.peek();
                list.add(tmp.val);
                if(tmp.left!=null){
                    
                    queue.add(tmp.left);
                    flag++;
                }
                if(tmp.right!=null){
                    queue.add(tmp.right);
                    flag++;
                }
                queue.poll();
                sum--;
            }
            sum = flag;
            ans.add(list);
        }
        return ans;
    }
    
}

发表于 2022-03-25 11:38:36 回复(0)

Java

624huiguorou

类似层序遍历，但又不完全是。区别在于需要把每层单独保存，所以说要获取每层的size，然后循环加入tempList，然后更新start和每层的size为end。从而实现每层单独加入。

public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> resList = new ArrayList<>();
        if(pRoot == null) return resList;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(pRoot);
        ArrayList<Integer> tempList = new ArrayList<>();
        int start = 0;
        int end = queue.size();
        //如何分段？通过queue里的size来分段
        while(!queue.isEmpty()){
            TreeNode tempNode = queue.pop();
            start++;
            tempList.add(tempNode.val);
            if(tempNode.left != null) queue.add(tempNode.left);
            if(tempNode.right != null) queue.add(tempNode.right);
            if(start == end){
                resList.add(tempList);
                tempList = new ArrayList<>();
                end = queue.size();
                start = 0;
            }
        }
        return resList;
    }
}

发表于 2022-03-08 10:50:19 回复(0)

Java

图南qqqq

import java.util.ArrayList;
import java.util.*;


/*
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>> lists = new ArrayList<>();
        if (pRoot == null) return lists;
        ArrayList<Integer> list;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(pRoot);
        
        while (!q.isEmpty()){
            int size = q.size();
            list = new ArrayList<>();
            while (size>0){
                TreeNode node = q.poll();
                list.add(node.val);
                if (node.left!=null) q.offer(node.left);
                if (node.right!=null) q.offer(node.right);
                size--;
            }
            lists.add(list);
        }
        return lists;
    }
    
}

发表于 2022-03-07 10:48:00 回复(0)

Java

DQING

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);
        queue.add(pRoot);
        //记录每一层的节点数
        int count = queue.size();
        while(!queue.isEmpty()) {
        	while(count > 0) {
	        	TreeNode node = queue.remove(0);//左右
		        if(node.left!=null) {
		        	queue.add(node.left);
		        	temp.add(node.left.val); 
		        }
		        if(node.right!=null) {
		        	queue.add(node.right);
		        	temp.add(node.right.val);
		        }
		        count--;
        	}
            if(!temp.isEmpty())
	        result.add(temp);//父，左右，左右左右
	        temp = new ArrayList<Integer>();
	        count = queue.size();
        }
        return result;
    } 
}

发表于 2022-01-29 16:51:32 回复(0)

Java

万里归途

import java.util.*;


/*
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>> res=new ArrayList<>();
    ArrayList<ArrayList<Integer> > Print(TreeNode root) {
         // write code here
        if(root==null){
            return res;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int n=queue.size();
            ArrayList<Integer> tem=new ArrayList<>();
            for(int i=0;i<n;i++){
                TreeNode cur=queue.poll();
                tem.add(cur.val);
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
            }
            res.add(tem);
        }
        return res;
    
    }
    
}

发表于 2022-01-29 11:30:51 回复(0)

Java

浮鸟(BAT实习ing，目标外企~)

import java.util.*;
public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        // 解法1：队列+同时出入队
        
        // 定义返回母list和辅助队列deque
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        // 判空
        if(pRoot==null){
            return ret;
        }
        // 根节点先入队
        deque.addLast(pRoot);
        // while遍历，条件是deque非空
        while(!deque.isEmpty()){
            // while每遍历一次，都会生成好一层的子list
            ArrayList<Integer> arr = new ArrayList<>();
            // 切记不要在for内部直接使用deque.size()，这样会动态增加每次遍历的长度
            int layerSize = deque.size();
            // for循环遍历deque
            for(int i=0;i<layerSize;i++){
                // 本层先出队，存入本层list
                TreeNode cur = deque.removeFirst();
                arr.add(cur.val);
                // 下层left和right再入队
                if(cur.left!=null){
                    deque.addLast(cur.left);
                }
                if(cur.right!=null){
                    deque.addLast(cur.right);
                }
            }
            // 母list存储本层子list
            ret.add(arr);
        }
        // 返回母list
        return ret;
    }
}

发表于 2022-01-05 20:23:40 回复(1)

Java

是小王吖🐅

 ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> list=new ArrayList();
        Deque<TreeNode> deque=new ArrayDeque();
        if(pRoot==null)return list;
        deque.push(pRoot);
        int size=1;
        int nextsize=0;
        while(!deque.isEmpty()){
            ArrayList<Integer> sublist=new ArrayList();
            for(int i=0;i<size;i++){
                TreeNode tmp=deque.poll();
                sublist.add(tmp.val);
                if(tmp.left!=null){
                    deque.offer(tmp.left);
                    nextsize++;
                }
                if(tmp.right!=null){
                    deque.offer(tmp.right);
                    nextsize++;
                }
            }
            list.add(sublist);
            size=nextsize;
            nextsize=0;
            
        }
        return list;
    }

发表于 2021-12-31 12:05:18 回复(0)

Java

heake

// 用两个队列分别临时存放上下两层的节点

ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
  ArrayList<ArrayList<Integer>> result = new ArrayList<>(); if (pRoot == null) { return result;
  }

  Queue<TreeNode> queue1 = new LinkedList<>();
  Queue<TreeNode> queue2 = new LinkedList<>();
  queue1.offer(pRoot); while (!queue1.isEmpty() || !queue2.isEmpty()) {
    ArrayList<Integer> list1 = new ArrayList<>(); while (!queue1.isEmpty()) {
      TreeNode node = queue1.poll();
      list1.add(node.val); if (node.left != null) {
        queue2.offer(node.left);
      } if (node.right != null) {
        queue2.offer(node.right);
      }
    } if (!list1.isEmpty()) {
      result.add(list1);
    }

    ArrayList<Integer> list2 = new ArrayList<>(); while (!queue2.isEmpty()) {
      TreeNode node = queue2.poll();
      list2.add(node.val); if (node.left != null) {
        queue1.offer(node.left);
      } if (node.right != null) {
        queue1.offer(node.right);
      }
    } if (!list2.isEmpty()) {
      result.add(list2);
    }
  } return result;
}

发表于 2021-12-28 21:39:49 回复(0)

Java

YajieC

import java.util.*;


/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    LinkedList<TreeNode> duiLie = new LinkedList<>();
    ArrayList<ArrayList<Integer>> returnList = new ArrayList<>();
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        if(pRoot == null){
            return returnList;
        }else{
            duiLie.add(pRoot);
        }
        int cenNum = 0;
        TreeNode del = null;
        while(!duiLie.isEmpty()){
            // 这一层的结点数目
            cenNum = duiLie.size();
            // 这一层 节点出队
            ArrayList<Integer> list = new ArrayList<>();
            for(int i = 0; i < cenNum; i++){
                del = duiLie.removeFirst();
                list.add(del.val);
                if(del.left != null){
                    duiLie.add(del.left);
                }
                if(del.right != null){
                    duiLie.add(del.right);
                }
            }
            returnList.add(list);
        }
        return returnList;
    }
    
}

发表于 2021-12-22 14:24:30 回复(0)

Java

^ǒ^月亮船^

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) {
        
        if(pRoot == null){
            return null;
        }
        
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        
        method(list, 1, pRoot);
        
        return list;
    }
    
    //从上到下按层从左至右打印二叉树
    public void method(ArrayList<ArrayList<Integer>> list, int deep, TreeNode pRoot){
        if(pRoot == null){
            return;
        }
        
        if(deep > list.size()){
            list.add(new ArrayList<Integer>());
        }
        list.get(deep -1).add(pRoot.val);
        
        method(list, deep + 1, pRoot.left);
        method(list, deep + 1, pRoot.right);
    }
    
}

发表于 2021-09-07 13:52:16 回复(0)

Java

谁是谁的眼

ArrayList<ArrayList<Integer> > Print(TreeNode root) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();

if(root == null){
return res;
}

Deque<TreeNode> queue = new LinkedList<>();

queue.offer(root);
List<Integer> list = new ArrayList<>();
TreeNode right = root;

while(!queue.isEmpty()){
TreeNode p = queue.poll();
list.add(p.val);

if(p.left != null){
queue.offer(p.left);
}
if(p.right != null){
queue.offer(p.right);
}

if(p == right){
right = queue.peekLast();
res.add(new ArrayList(list));
list.clear();
list.clear();
}
}

return res;
}

发表于 2021-08-22 21:37:40 回复(0)

Java

together"

import java.util.ArrayList;
import java.util.Queue;
import java.util.ArrayDeque;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {

    // 层次遍历, 说白了就是分层的BFS
    // 时间复杂度O(n)
    // 空间复杂度O(n)
    ArrayList<ArrayList<Integer>> Print(TreeNode root) {
        if (root == null) {
            return new ArrayList<>(0);
        }

        ArrayList<ArrayList<Integer>> resultList = new ArrayList<>();
        Queue<TreeNode> qu = new ArrayDeque<>();
        qu.add(root);

        while (!qu.isEmpty()) {
            ArrayList<Integer> rowList = new ArrayList<>();
            resultList.add(rowList);
            int size = qu.size();
            while (size > 0) {
                TreeNode p = qu.remove();
                rowList.add(p.val);
                if (p.left != null) {
                    qu.add(p.left);
                }
                if (p.right != null) {
                    qu.add(p.right);
                }
                size--;
            }
        }

        return resultList;
    }

}

发表于 2021-08-19 10:26:29 回复(0)

Java

QAQWQAQ

     ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
         ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
        
         if (pRoot == null) return arrayLists;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(pRoot);
        while (!queue.isEmpty()) {
            int size = queue.size();
            ArrayList<Integer> integers = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode temp = queue.poll();
                integers.add(temp.val);
                if(temp.left!=null)
                    queue.offer(temp.left);
                if(temp.right!=null)
                    queue.offer(temp.right);
            }
            arrayLists.add(integers);
        }

        return arrayLists;
    }

发表于 2021-08-18 18:58:45 回复(0)

提交观点

问题信息

树广度优先搜索(BFS)

难度：

155条回答 845收藏 82802浏览

通过挑战的用户

查看代码

牛客30382...

2022-12-24 16:35:12
想成为大佬的小菜鸡

2022-09-16 17:30:01
Levi丶acm

2022-09-16 16:25:46
牛客61414...

2022-09-16 16:09:38
新ちゃん

2022-09-16 10:39:29

把二叉树打印成多行

输入描述:

输入

输出

输入

输出

输入

输出

输入

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题