给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
例如：
给定的二叉树是{3,9,20,#,#,15,7},
该二叉树层序遍历的结果是
[
[3],
[9,20],
[15,7]
]
提示:
0 <= 二叉树的结点数 <= 1500
[编程题]求二叉树的层序遍历
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
// write code here
ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
ArrayList<Integer> level = new ArrayList<>();
Queue<TreeNode> queue = new ArrayDeque<>();
if(root == null){
return ret;
}
TreeNode curEnd = root;
queue.add(root);
TreeNode nextEnd = null;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) {
queue.add(node.left);
nextEnd = node.left;
}
if (node.right != null) {
queue.add(node.right);
nextEnd = node.right;
}
if (node == curEnd) {
ret.add(level);
level = new ArrayList<>();
curEnd = nextEnd;
}
}
return ret;
}
编辑于 2024-02-06 10:59:29
回复(0)
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
// write code here
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(root == null){
return res;
}
ArrayList<TreeNode> listCru = new ArrayList<>();
listCru.add(root);
int count = 0;
int n=1;
while(count < n){
n = listCru.size();
ArrayList<Integer> listres = new ArrayList<>();
for(;count<n;count++){
listres.add(listCru.get(count).val);
if(listCru.get(count).left != null){
listCru.add(listCru.get(count).left);
}
if(listCru.get(count).right != null){
listCru.add(listCru.get(count).right);
}
}
n = listCru.size();
res.add(listres);
}
return res;
}
发表于 2023-10-19 11:11:23
回复(0)
public class Solution {
/**
* 给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
*
*
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
if (null == root) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
ArrayList<Integer> currList = new ArrayList<>();
int rootSize = queue.size();
while (!queue.isEmpty()) {
TreeNode top = queue.poll();
currList.add(top.val);
if (top.left != null) {
queue.offer(top.left);
}
if (top.right != null) {
queue.offer(top.right);
}
//如果当前层数的所有节点存储完成
if (currList.size() == rootSize) {
result.add(currList);
currList = new ArrayList<>();
//队列的size即为下层节点总数
rootSize = queue.size();
}
}
return result;
}
}
发表于 2023-10-12 16:30:14
回复(0)
import java.util.*;public class Solution { ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>(); /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型ArrayList<ArrayList<>> */ public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) { // write code here layer(root, 0); return ans; } public void layer (TreeNode root, int layerNum){ ArrayList<Integer> temp = new ArrayList<Integer>(); if(root == null){ return; } if(ans.size() <= layerNum){ temp.add(root.val); ans.add(temp); }else{ ans.get(layerNum).add(root.val); } layer(root.left, layerNum + 1); layer(root.right, layerNum + 1); } }
发表于 2023-09-24 16:36:24
回复(0)
没想到什么好的办法来记录树的行数
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<TreeNode> list = new ArrayList<TreeNode>();
ArrayList<Integer> listHor = new ArrayList<Integer>();
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
// write code here
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
// list用来将Tree转换成队列
list = new ArrayList<TreeNode>();
// listHor用来储存Tree的行数
listHor = new ArrayList<Integer>();
if (root == null) {
return result;
}
list.add(root);
listHor.add(0);
int count = 1;
int j = 0;
ArrayList<Integer> res = new ArrayList<Integer>();
int oldIndex = 0;
for (int i = 0; i < list.size(); i++) {
// 确认现在的行数
int index = listHor.get(i);
// 如果换行了，就将res添加到result中
if (index != oldIndex) {
if (!res.isEmpty()) {
result.add(res);
}
res = new ArrayList<Integer>();
oldIndex = index;
}
// 获取Node，并将它的孩子放入队列中，同时根据现在的行数添加其孩子的行数
TreeNode node = list.get(i);
if (node.left != null) {
list.add(node.left);
listHor.add(index + 1);
}
if (node.right != null) {
list.add(node.right);
listHor.add(index + 1);
}
// 添加到res中
res.add(node.val);
}
result.add(res);
return result;
}
}
发表于 2023-08-28 12:23:13
回复(0)
class Solution:
def levelOrder(self , root: TreeNode) -> List[List[int]]:
# write code here
if root == None:
return []
que = []
que.append(root)
reslut = []
while len(que) != 0:
temp = []
n = len(que)
for i in range(n):
root = que.pop(0)
temp.append(root.val)
if root.left != None:
que.append(root.left)
if root.right != None:
que.append(root.right)
reslut.append(temp)
return reslut
发表于 2023-08-09 11:25:55
回复(0)
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
* 用BFS做---队列--------广度遍历算法
*/
ArrayList<ArrayList<Integer>> arrys = null;
//尝试用递归来做
private void doFunction(TreeNode node,int index){
if(node==null){
return;
}
//注意这里用>=不能用==,>=表示该层已经创建，直接添加数据到集合即可
if(arrys.size()>=index){
ArrayList<Integer> arry = arrys.get(index-1);
arry.add(node.val);
arrys.set(index-1,arry);
//代表存储该层数据的集合未创建，需创建新子集合
}else{
ArrayList<Integer> arry = new ArrayList<>();
arry.add(node.val);
arrys.add(arry);
}
doFunction(node.left,index+1);
doFunction(node.right,index+1);
}
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
arrys = new ArrayList<>();
//执行递归
this.doFunction(root,1);
return arrys;
}
}
发表于 2023-08-07 11:25:19
回复(0)
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 {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
// write code here
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new ArrayDeque<TreeNode>();
q.add(root);
while (!q.isEmpty()) {
ArrayList<Integer> row = new ArrayList<>();
int n = q.size();
for (int i = 0; i < n; i++) {
TreeNode temp = q.poll();
row.add(temp.val);
if (temp.left != null) q.add(temp.left);
if (temp.right != null) q.add(temp.right);
}
res.add(row);
}
return res;
}
}
发表于 2023-07-22 20:26:28
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
*/
private Map<Integer, ArrayList<Integer>> retMap = new
HashMap<Integer, ArrayList<Integer>>(16);
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
// write code here
ArrayList<ArrayList<Integer>> retList = new ArrayList<>(16);
//从根节点开始
levelOrderNext(root, 0);
int i = 0;
Iterator<Map.Entry<Integer, ArrayList<Integer>>> iterator = retMap.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<Integer, ArrayList<Integer>> next = iterator.next();
retList.add(next.getValue());
}
return retList;
}
//层级遍历，递归完成。简单易理解
public void levelOrderNext(TreeNode root, int num) {
if (root == null) {
return;
}
if (retMap.get(num) == null) {
ArrayList<Integer> list = new ArrayList<>(8);
list.add(root.val);
retMap.put(num, list);
} else {
ArrayList<Integer> list = retMap.get(num);
list.add(root.val);
retMap.put(num, list);
}
TreeNode leftNode = root.left;
TreeNode rightNode = root.right;
num++;
levelOrderNext(leftNode, num);
levelOrderNext(rightNode, num);
}
}
发表于 2023-04-19 17:18:27
回复(0)
/**
*
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
// write code here
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
level(root,list,0);
return list;
}
public void level (TreeNode root,ArrayList<ArrayList<Integer>> list,int i) {
// write code here
if(root!=null){
if(list.size()==i){
list.add(i,new ArrayList<Integer>());
}
list.get(i).add(root.val);
level(root.left,list,i+1);
level(root.right,list,i+1);
}
}
发表于 2023-03-07 22:17:12
回复(0)
public class Solution {
/**
*
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
return bfs(root);
}
private ArrayList<ArrayList<Integer>> bfs(TreeNode root) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Deque<TreeNode> queue = new LinkedList<>();
queue.offerLast(root);
int size;
while (!queue.isEmpty()) {
ArrayList<Integer> list = new ArrayList<>();
size = queue.size();
for (int i = 0; i <= size - 1; i++) {
TreeNode u = queue.pollFirst();
list.add(u.val);
if (u.left != null) {
queue.offerLast(u.left);
}
if (u.right != null) {
queue.offerLast(u.right);
}
}
result.add(list);
}
return result;
}
}
发表于 2023-02-15 23:43:30
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
// write code here
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
ArrayList<Integer> list = new ArrayList<>();
int size = queue.size();
while (size > 0) {
TreeNode poll = queue.poll();
list.add(poll.val);
if (poll.left != null) {
queue.offer(poll.left);
}
if (poll.right != null) {
queue.offer(poll.right);
}
size -- ;
}
result.add(list);
}
return result;
}
}
发表于 2022-11-04 22:44:09
回复(0)
使用一个队列 保存所有节点的值
public class Solution {
/**
*
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
// write code here
// 定义返回值
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
if (root == null){// 传入根节点为空，返回空结果
return result;
}
// 使用LinkedList 当作队列，用于存储遍历到的树节点
LinkedList<TreeNode> linked = new LinkedList<>();
linked.add(root); // 首先在队列里添加根节点
int size; // 用于存储每次获取的链表长度
TreeNode temp; // 临时节点
// 只要链表不为空，while继续
while (!linked.isEmpty()){
// 获取链表的长度
size = linked.size();
// 创建一个list，用于存储当前层的节点值
ArrayList<Integer> line = new ArrayList<>();
// 链表有几个元素 就循环几次
for(int i = 0; i < size; i++){
// 删除链表头节点，并且将删除的元素返回 (类似于栈的pop，弹出一个元素)
temp = linked.removeFirst();
// 将当前层的节点值保存
line.add(temp.val);
// left节点不为空 就将left节点添加进链表，作为下一层
if(temp.left != null){
linked.add(temp.left);
}
// right节点不为空，就将right节点添加进链表，作为下一层
if(temp.right != null){
linked.add(temp.right);
}
}
// 上面的for循环结束的时候，实际上就已经根据size取出当前层的所有节点，并且存储进了line里，并且也把当前层的所有节点 的 子节点 存入了链表，下次循环会重新计算链表的长度
// 将当前层的所有节点值集合存入result中
result.add(line);
}
// while结束，说明树已经遍历结束，返回result
return result;
}
}
发表于 2022-11-02 14:01:28
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
// write code here
LinkedList<TreeNode> l = new LinkedList();
l.push(root);
ArrayList<ArrayList<Integer>> in1 = new ArrayList();
while(!l.isEmpty()){
List<TreeNode> t = new ArrayList();
ArrayList<Integer> ints = new ArrayList();
while(!l.isEmpty()){
TreeNode node = l.pop();
ints.add(node.val);
if(null!=node.left)
t.add(node.left);
if(null!=node.right)
t.add(node.right);
}
in1.add(ints);
l.addAll(t);
}
return in1;
}
}
发表于 2022-09-03 18:07:53
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
// write code here
// write code here
ArrayList<ArrayList<Integer>> list=new ArrayList<>();
TreeNode cursor_1=root;
if(cursor_1==null){
return list;
}
Deque<TreeNode> deque=new LinkedList<>();
deque.push(cursor_1);
int length=1;
while(!deque.isEmpty()){
int num=0;
int nextlength=0;
ArrayList<Integer> sublist=new ArrayList<>();
while(num<length&&(!deque.isEmpty())){
cursor_1=deque.poll();
sublist.add(cursor_1.val);
if(cursor_1.left!=null){
deque.addLast(cursor_1.left);
nextlength++;
}
if(cursor_1.right!=null){
deque.addLast(cursor_1.right);
nextlength++;
}
num++;
}
list.add(sublist);
length=nextlength;
}
return list;
}
}
发表于 2022-08-30 00:15:40
回复(0)
BFS实现层序遍历
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
// write code here
ArrayList<ArrayList<Integer>> ans=new ArrayList<>();
Deque<TreeNode> deque=new ArrayDeque<>();
deque.addLast(root);
while(!deque.isEmpty()){
int size=deque.size();
ArrayList<Integer> list=new ArrayList<>();
while(size-->0){
TreeNode cur=deque.pollFirst();
list.add(cur.val);
if(cur.left!=null) deque.addLast(cur.left);
if(cur.right!=null) deque.addLast(cur.right);
}
ans.add(list);
}
return ans;
}
发表于 2022-08-26 14:26:13
回复(0)
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
//使用dummyNode(哨兵节点)的方法
//如列题的3，9，20，15，7
//第一层3，在后面加一个null，第二层9，20，后面加一个null，第三层15，7，加一个null
//最后得：3，null，3，20，null，15，7，null
//每次判断节点为null，则在队列尾端加一个null，如果节点不是null，则把该节点左右孩子加入队列
//一开始我们初始化队列为：3，null，好比如 root节点3，不是空，将节点3的左右孩子节点加入队列
//并将节点3加入列表list，得null，9，20（3节点遍历完去掉，即poll方法），循环到null节点（表明一层结束）
//要清空list，并在队列尾部加上个null节点
//每一层结束加一个null节点
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if(root==null){
return result;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
queue.offer(null);
ArrayList<Integer> list = new ArrayList<Integer>();
while(!queue.isEmpty()){
TreeNode node = queue.poll();
if(node==null){
//一层结束,并且将这一层的节点值放在list
if(list.size()==0){//这是为了处理最后一个节点
break;
}
result.add(list);
list = new ArrayList<Integer>();
queue.offer(null);
continue;
}
list.add(node.val);
if(node.left!=null){
queue.offer(node.left);
}
if(node.right!=null){
queue.offer(node.right);
}
}
return result;
// write code here
}
发表于 2022-08-24 10:55:42
回复(0)
使用队列
我们数据结构的书上教的层序遍历,就是利用一个队列,不断的把左子树和右子树 入队。但是这个题目还要要求按照层输出。所以关键的问题是： 如何确定是在 同一层的。 如果在入队之前,把上一层所有的节点出队,那么出队的这些节点就是上一层的列表。
public ArrayList<ArrayList<Integer>> levelOrder_iterate (TreeNode root) {
// write code here
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
int sz = queue.size();
ArrayList<Integer> levelRes = new ArrayList<>(sz);
for (int i = 0; i<sz; i++) {
TreeNode pNode = queue.poll();
levelRes.add(pNode.val);
if (pNode.left != null) {
queue.offer(pNode.left);
}
if (pNode.right != null) {
queue.offer(pNode.right);
}
}
res.add(levelRes);
}
return res;
} 递归方式
题目要求按照层序遍历输出数据，并且区分不同层；可以认为是按照深度进行的输出，第0层处于结果数组的index=0；
// 对于节点，按照深度加入到结果数组中
private void levelOrderHelper(ArrayList<ArrayList<Integer>> res, TreeNode root, int depth) {
if (root == null) {
return ;
}
if (res.size() == depth) {
res.add(new ArrayList<>());
}
res.get(depth).add(root.val);
levelOrderHelper(res, root.left, depth+1);
levelOrderHelper(res, root.right, depth+1);
}
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
this.levelOrderHelper(res, root, 0);
return res;
}
发表于 2022-08-17 15:07:48
回复(0)
public class Solution {
/**
*
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
*/
int max = 1;
ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
// write code here
getDepth(root,1);
for (int i = 0; i < max; i++) {
lists.add(new ArrayList<Integer>());
}
rootDfs(root,0);
return lists;
}
private void rootDfs(TreeNode root, int i) {
if (root == null) {
return;
}
ArrayList<Integer> list = lists.get(i);
list.add(root.val);
if (root.left != null) {
rootDfs(root.left,i + 1);
}
if (root.right != null) {
rootDfs(root.right,i + 1);
}
}
private void getDepth(TreeNode root, int i) {
if (root == null) {
return;
}
max = Math.max(max,i);
if (root.left != null) {
getDepth(root.left,i + 1);
}
if (root.right != null) {
getDepth(root.right,i + 1);
}
}
}
写的 辣鸡
发表于 2022-08-15 10:27:57
回复(0)
问题信息
难度：
112条回答
1099收藏
34943浏览
通过挑战的用户
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
