给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
例如：
给定的二叉树是{3,9,20,#,#,15,7},
该二叉树层序遍历的结果是
[
[3],
[9,20],
[15,7]
]
提示:
0 <= 二叉树的结点数 <= 1500
[编程题]求二叉树的层序遍历
/**
* 使用队列来解决，先进先出
*/
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
ArrayList<ArrayList<Integer>> res=new ArrayList<>();
Queue<TreeNode> queue=new LinkedList<>();
if(root==null){
return res;
}
queue.add(root);
while (!queue.isEmpty()){
ArrayList<Integer> list=new ArrayList<>();
//确定层数 第一层1个、第二层2个
int len=queue.size();
for (int i = 0; i < len; i++) {
TreeNode node = queue.poll();
list.add(node.val);
if(node.left!=null){
queue.add(node.left);
}
if(node.right!=null){
queue.add(node.right);
}
}
res.add(list);
}
return res;
}
发表于 2021-08-03 22:12:47
回复(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
if(root==null)
return new ArrayList(new ArrayList());
ArrayList<ArrayList<Integer>> ans=new ArrayList<>();
Queue<TreeNode> q=new LinkedList<>();
q.add(root);
while(!q.isEmpty()){
Queue<TreeNode> t=new LinkedList<>();
while(!q.isEmpty())
t.add(q.poll());
ArrayList<Integer> abs=new ArrayList<>();
while(!t.isEmpty()){
TreeNode node=t.poll();
abs.add(node.val);
if(node.left!=null)
q.add(node.left);
if(node.right!=null)
q.add(node.right);
}
ans.add(abs);
}
return ans;
}
}
发表于 2021-07-19 23:32:10
回复(0)
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
// write code here
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
//一定要注意这句，不加就是空指针异常
if(root!=null){
Queue<TreeNode> qu=new LinkedList<>();
qu.offer(root);
while(!qu.isEmpty()){
ArrayList<Integer> list2=new ArrayList<>();
int size=qu.size();
while(size>0){
TreeNode cur=qu.poll();
list2.add(cur.val);
size--;
if(cur.left!=null){
qu.offer(cur.left);
}
if(cur.right!=null){
qu.offer(cur.right);
}
}
list.add(list2);
}
}
return list;
}
发表于 2021-05-31 00:26:26
回复(0)
二叉树的遍历可以考虑递归实现，其中层次遍历与其二叉树深度有关，所以可以设计一个深度计数器，每次递归时计数器加1。
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
// write code here
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(root == null)
return res;
DFS(root,res,0);
return res;
}
public void DFS(TreeNode root, ArrayList<ArrayList<Integer>> list, int depth){
if(root == null) return;
if(list.size() == depth) list.add(new ArrayList<>());
DFS(root.left, list, depth + 1);
list.get(depth).add(root.val);
DFS(root.right, list, depth + 1);
}
发表于 2021-04-16 10:31:45
回复(0)
/*
* function TreeNode(x) {
* this.val = x;
* this.left = null;
* this.right = null;
* }
*/
/**
*
* @param root TreeNode类
* @return int整型二维数组
*/
function levelOrder( root ) {
// write code here
let res=[];
if(!root){
return [];
}
function tra(node,depth){
if(!res[depth]){
res[depth]=[];
}
res[depth].push(node.val);
if(node.left){
tra(node.left,depth+1);
}
if(node.right){
tra(node.right,depth+1);
}
}
tra(root,0);
return res;
}
module.exports = {
levelOrder : levelOrder
};
发表于 2021-04-06 16:37:45
回复(0)
function levelOrder( root ) {
const res = [];
if (!root) return res;
const queue = [root];
while (queue.length > 0) {
res.push(queue.map(i => i.val));
let len = queue.length;
while (len) {
const cur = queue.shift();
if (cur.left) queue.push(cur.left);
if (cur.right) queue.push(cur.right);
len--;
}
}
return res;
}
发表于 2021-04-02 17:10:59
回复(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<>>
*/
/*基本思想：使用2个变量记录当前层还未打印节点的数量以及下一层需要打印节点的数量*/
/*其他思路：1）while里面嵌套for循环，for循环的大小为当前层的大小
2）采用2个队列，还有一个队列用于保存当前的层数*/
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
if(root == null)
return res;
Deque<TreeNode> queue = new LinkedList<TreeNode>();
queue.addLast(root);
ArrayList<Integer> tmp = new ArrayList<Integer>();
int num = 1; // 当前层还需打印的节点数量
int ans = 0; // 下一层累加的节点数量
while(!queue.isEmpty()){
TreeNode cur = queue.removeFirst();
--num;
tmp.add(cur.val);
if(cur.left != null){
queue.add(cur.left);
++ans;
}
if(cur.right != null){
queue.add(cur.right);
++ans;
}
if(num == 0){
res.add(tmp);
tmp = new ArrayList<Integer>();
num = ans;
ans = 0;
}
}
return res;
}
}
发表于 2021-04-01 23:52:01
回复(0)
思路:
一层一层的去遍历
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
// write code here
ArrayList<ArrayList<Integer>> res = new ArrayList<>(); //存答案
if(root==null) return res;
ArrayList<TreeNode> level=new ArrayList<>(); //用来存当前的树的层
level.add(root);
while(!level.isEmpty()){
ArrayList<TreeNode> tmp = new ArrayList<>(); //创建临时的层，用来存放下一层
ArrayList<Integer> resLevel= new ArrayList<>(); //用来存放当前层的结果
for(TreeNode node:level){
resLevel.add(node.val); //将当前层的结果塞进去
if(node.left!= null) tmp.add(node.left); //同时看当前层的左右孩子，存进tmp
if(node.right!=null) tmp.add(node.right);
}
level=tmp; //用tmp覆盖当前层，下一轮循环将是下一层了
res.add(resLevel); //别忘了存放当前层的结果。
}
return res;
}
}
发表于 2021-01-22 01:03:21
回复(0)
层序遍历思路就是借助队列的特性来实现
整体思路为
节点入队，队列不为空循环，出队则打印，并顺序入队左右子节点。
需要把层分出来有两种思路：
借助 Map 存储每个节点层数（已知根节点为 1）
不借助 Map 当前层最后节点，和下一层最后节点（已知跟节点为当前层最后节点）
算法如下：
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>> levelOrderWithMap (TreeNode root) {
// write code here
Queue<TreeNode> queue=new LinkedList<>();
Map<TreeNode,Integer> levelMap=new HashMap<>(16);
ArrayList<ArrayList<Integer>> result=new ArrayList<>(16);
if(root==null){
return result;
}
levelMap.put(root,1);
int currentLevel=1;
ArrayList<Integer> currentLevelNodesArray=new ArrayList<>(16);
result.add(currentLevelNodesArray);
queue.add(root);
while (!queue.isEmpty()){
TreeNode treeNode=queue.poll();
//获取当前出队节点level
int currentNodeLevel=levelMap.get(treeNode);
System.out.println(treeNode.val);
if (treeNode.left!=null){
levelMap.put(treeNode.left,currentNodeLevel+1);
queue.add(treeNode.left);
}
if (treeNode.right!=null){
levelMap.put(treeNode.right,currentNodeLevel+1);
queue.add(treeNode.right);
}
if (currentLevel!=currentNodeLevel){
//已经是下一层生成新列表
currentLevel++;
currentLevelNodesArray=new ArrayList<>(16);
result.add(currentLevelNodesArray);
}
currentLevelNodesArray.add(treeNode.val);
}
return result;
}
/**
* 不借助 map 解法
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
*/
public static ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
// write code here
Queue<TreeNode> queue=new LinkedList<>();
ArrayList<ArrayList<Integer>> result=new ArrayList<>(16);
if(root==null){
return result;
}
//记录当前层最后一个节点，整个算法是基于我已知根节点是第一层最后一个节点
TreeNode currentEndNode=root;
//记录下一层最后一个节点
TreeNode nextEndNode=null;
ArrayList<Integer> currentLevelNodesArray=new ArrayList<>(16);
result.add(currentLevelNodesArray);
queue.add(root);
while (!queue.isEmpty()){
TreeNode curNode=queue.poll();
//获取当前出队节点level
if (curNode.left!=null){
queue.add(curNode.left);
//如果有左节点更新下一层最后节点
nextEndNode=curNode.left;
}
if (curNode.right!=null){
queue.add(curNode.right);
nextEndNode=curNode.right;
}
//不由分说先入队
currentLevelNodesArray.add(curNode.val);
//如果当前出队节点是当前层最后一个节点
//生成新列表 更新当前层最后节点
if (curNode==currentEndNode){
//已经是下一层生成新列表
currentLevelNodesArray=new ArrayList<>(16);
result.add(currentLevelNodesArray);
currentEndNode=nextEndNode;
}
}
result.remove(result.size()-1);
return result;
}
}
发表于 2020-11-28 10:32:13
回复(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) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
Queue<TreeNode> q1 = new LinkedList<>();
Queue<TreeNode> q2 = new LinkedList<>();
ArrayList<Integer> list;
if(root != null) {
q1.add(root);
}
TreeNode node;
// 每一层作为一次循环，q1作为奇数层的节点存储；q2作为偶数层的节点存储
while(q1.size() > 0 || q2.size() > 0) {
list = new ArrayList<Integer>();
while(q1.size() > 0) {
node = q1.poll();
list.add(node.val);
if(node.left != null) {
q2.add(node.left);
}
if(node.right != null) {
q2.add(node.right);
}
}
if(list.size() > 0) {
result.add(list);
}
list = new ArrayList<Integer>();
while(q2.size() > 0) {
node = q2.poll();
list.add(node.val);
if(node.left != null) {
q1.add(node.left);
}
if(node.right != null) {
q1.add(node.right);
}
}
if(list.size() > 0) {
result.add(list);
}
}
return result;
}
}
发表于 2020-11-15 22:52:12
回复(0)
package main
import . "nc_tools"
/*
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/**
*
* @param root TreeNode类
* @return int整型二维数组
*/
func levelOrder( root *TreeNode ) [][]int {
// write code here
ret := make([][]int, 0)
tmp := make([]int, 0)
nodeList := make([]*TreeNode, 0)
if root == nil {
return ret
}
nodeList = append(nodeList, root)
for i, listLen := 0, len(nodeList); i<listLen; {
tmp = append(tmp, nodeList[i].Val)
if nodeList[i].Left != nil {
nodeList = append(nodeList, nodeList[i].Left)
}
if nodeList[i].Right != nil {
nodeList = append(nodeList, nodeList[i].Right)
}
if i == listLen - 1 {
ret = append(ret, tmp)
tmp = tmp[len(tmp):]
nodeList = nodeList[listLen:]
i = 0
listLen = len(nodeList)
} else {
i++
}
}
return ret
import . "nc_tools"
/*
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/**
*
* @param root TreeNode类
* @return int整型二维数组
*/
func levelOrder( root *TreeNode ) [][]int {
// write code here
ret := make([][]int, 0)
tmp := make([]int, 0)
nodeList := make([]*TreeNode, 0)
if root == nil {
return ret
}
nodeList = append(nodeList, root)
for i, listLen := 0, len(nodeList); i<listLen; {
tmp = append(tmp, nodeList[i].Val)
if nodeList[i].Left != nil {
nodeList = append(nodeList, nodeList[i].Left)
}
if nodeList[i].Right != nil {
nodeList = append(nodeList, nodeList[i].Right)
}
if i == listLen - 1 {
ret = append(ret, tmp)
tmp = tmp[len(tmp):]
nodeList = nodeList[listLen:]
i = 0
listLen = len(nodeList)
} else {
i++
}
}
return ret
}
解题思路：
1、使用一个Slice(上面代码中的nodeList)充当队列的作用，每次将每层的节点入队，每层的节点入队完后在出队将出队的节点的值追加到同一个一维的int类型的Slice，然后将这个临时的Slice追加到int类型的二维Slice。
2、注意上面代码中的nodeList，提前计算了队列长度，所以知道当前层有几个节点，所有后续当前层的左右孩子节点可以继续追加到该队列中，使用完当前层的所有节点后，再统一出队（删除），如此循环。
发表于 2020-08-21 18:22:38
回复(0)
class Solution {
public:
vector<vector<int> > levelOrder(TreeNode *root) {
vector<vector<int> > orders;
if(root == NULL)
return orders;
int level = 1;
queue<TreeNode *> q1,q2;
q1.push(root);
while(!q1.empty() || !q2.empty()){
if(level % 2 == 1){
vector<int> res;
while(!q1.empty()){
TreeNode *p = q1.front();
res.push_back(p->val);
q1.pop();
if(p->left)
q2.push(p->left);
if(p->right)
q2.push(p->right);
}
orders.push_back(res);
level++;
}
else{
vector<int> res;
while(!q2.empty()){
TreeNode *p = q2.front();
res.push_back(p->val);
q2.pop();
if(p->left)
q1.push(p->left);
if(p->right)
q1.push(p->right);
}
orders.push_back(res);
level++;
}
}
return orders;
}
};
发表于 2020-04-27 12:41:28
回复(0)
import java.util.ArrayList;
public class Solution {
/**
* 递归的方式实现
*/
public ArrayList<ArrayList<Integer>> levelOrder1(TreeNode root) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
if (root == null)
return result;
recursionHelper(result, 0, root);
return result;
}
private void recursionHelper(ArrayList<ArrayList<Integer>> result, int level, TreeNode root) {
if (root == null)
return;
// 遍历新的行
if (level == result.size()) {
ArrayList<Integer> levelResult = new ArrayList<>();
levelResult.add(root.val);
result.add(levelResult);
} else { // 已经遍历过的 level 行
ArrayList<Integer> levelResult = result.get(level);
levelResult.add(root.val);
result.set(level, levelResult);
}
// 遍历下一行
recursionHelper(result, level + 1, root.left);
recursionHelper(result, level + 1, root.right);
}
/**
* 非递归的方式，遍历当前层同时保存对应的左右节点
*/
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
if (root == null)
return result;
ArrayList<TreeNode> curLevel = new ArrayList<>();
curLevel.add(root);
while (!curLevel.isEmpty()) {
// 当前层的遍历结果
ArrayList<Integer> curResult = new ArrayList<>();
// 保存下一层的节点
ArrayList<TreeNode> nextLevel = new ArrayList<>();
for (TreeNode node : curLevel) {
curResult.add(node.val);
if (node.left != null)
nextLevel.add(node.left);
if (node.right != null)
nextLevel.add(node.right);
}
result.add(curResult);
curLevel = nextLevel;
}
return result;
}
}
发表于 2018-07-19 18:08:21
回复(0)
C++解法
层次遍历，使用循环，一层一层的访问该层的所有节点，并保存到result里面。
class Solution {
public:
vector <vector<int>> levelOrder(TreeNode *root) {
vector <vector<int>> result;
if (root == NULL) { return result ; }
vector <TreeNode*> nodeStack;
nodeStack.push_back(root);
while (nodeStack.size()) {
vector<int> value;
vector < TreeNode *> nextLevel;
for (int i = 0; i < nodeStack.size(); i++) {
value.push_back(nodeStack[i]->val);
}
for (int i = 0; i < nodeStack.size(); i++) {
if (nodeStack[i]->left) { nextLevel.push_back(nodeStack[i]->left); }
if (nodeStack[i]->right) { nextLevel.push_back(nodeStack[i]->right); }
}
nodeStack = nextLevel;
result.push_back(value);
}
return result;
}
};
发表于 2017-10-27 17:47:58
回复(0)
class Solution {
public:
vector<vector<int> > levelOrder(TreeNode *root) {
vector<vector<int> > list;
queue<TreeNode *> q;
queue<int> level; //记录每一层
int layer = 0; //记录当前所在层数
if(root == NULL)
return list;
TreeNode *cur = root;
q.push(cur);
level.push(0);
while(!q.empty())
{
cur = q.front(); //记录当前根
layer = level.front();
q.pop();
level.pop();
if(list.size() < layer+1)
{
vector<int> v;
list.push_back(v); //list新增一行
}
list[layer].push_back(cur->val);
if(cur->left != NULL) //左子树非空
{
q.push(cur->left);
level.push(layer+1);
}
if(cur->right != NULL) //右子树非空
{
q.push(cur->right);
level.push(layer+1);
}
}
return list;
}
};
发表于 2017-08-03 01:26:47
回复(0)
方法一：思路是通过每一层queue中的数量去换行
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(root==null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
ArrayList<Integer> list = new ArrayList<>();;
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode tmp = queue.poll();
if(tmp!=null){
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;
}
方法二:通过两个变量一个变量记录每一层最右边的变量 last，
另一个变量记录当前最新进入队列的节点 nlast，
当队列移除的节点是last记录的节点，也就是一层最右的节点时，
nlast赋值给last,此时恰好last又是最右,我们通过这个条件就可以实现换行了
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
ArrayList<Integer> list = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
TreeNode fflag = root;
TreeNode nowNode = root;
while (!queue.isEmpty()) {
TreeNode tmp = queue.poll();
//记录最新节点
if (tmp.left != null) {
queue.offer(tmp.left);
nowNode = tmp.left;
}
if (tmp.right != null){
queue.offer(tmp.right);
nowNode = tmp.right;
}
list.add(tmp.val);
//如果当前节点等于last节点说明换行
if(tmp == fflag){
fflag = nowNode;
lists.add(list);
list = new ArrayList<>();
}
}
return lists;
}
编辑于 2017-08-13 15:36:13
回复(0)
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
if(root == null)
return res;
ArrayList<Integer> list = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()){
int layerSize = queue.size();
while(layerSize-- != 0){
TreeNode temp = queue.poll();
list.add(temp.val);
if(temp.left != null) queue.add(temp.left);
if(temp.right != null) queue.add(temp.right);
}
res.add(new ArrayList<Integer>(list));
list.clear();
}
return res;
}
}
发表于 2017-05-17 19:54:27
回复(0)
//层序遍历
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
ArrayList<ArrayList<Integer>> result=new ArrayList<>();
Queue<TreeNode> queue=new LinkedList<>();
if(root==null) return result;
queue.add(root);
while(!queue.isEmpty()){
ArrayList<Integer> level=new ArrayList<>();
int len=queue.size();
while(len--!=0){
TreeNode temp=queue.poll();
level.add(temp.val);
if(temp.left!=null) queue.add(temp.left);
if(temp.right!=null) queue.add(temp.right);
}
result.add(level);
}
return result;
}
发表于 2017-05-02 14:07:03
回复(0)
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(root == null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while ( ! queue.isEmpty()) {
ArrayList<Integer> list = new ArrayList<>();
int size = queue.size();
for (int i = 0; i < size; i ++ ) {
TreeNode temp = queue.poll();
list.add(temp.val);
if(temp.left != null) queue.add(temp.left);
if(temp.right != null) queue.add(temp.right);
}
res.add(list);
}
return res;
}
}
发表于 2016-11-01 21:06:04
回复(0)
//层次遍历用队列比较方便。一个计数器记载当前层的节点个数，一个计数器记载上层节点个数
//for （...;i<上层节点;..）循环存储进vector<int>临时变量，结束之后存进vector<vector<int>> class Solution {
public:
vector<vector<int> > levelOrder(TreeNode *root) {
std::vector<std::vector<int>> vec;
if(root == NULL)
return vec;
std::queue<TreeNode> asisQueue;
asisQueue.push(*root);
int levelNodeNum = 1;
while(!asisQueue.empty()){
int tempNodeNum = levelNodeNum;
levelNodeNum = 0;
std::vector<int> tempVec;
for(int i = 0; i<tempNodeNum; i++){
TreeNode tmp = asisQueue.front(); asisQueue.pop();
tempVec.push_back(tmp.val);
if(tmp.left != NULL) {
asisQueue.push(*tmp.left); levelNodeNum++;
}
if(tmp.right != NULL) {
asisQueue.push(*tmp.right); levelNodeNum++;
}
}
vec.push_back(tempVec);
}
return vec;
}
};
发表于 2016-09-08 17:57:42
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
