给定一棵二叉树，返回齐自底向上的层序遍历。
数据范围：二叉树上节点数满足 
，二叉树上的值满足 
样例图：
[编程题]从下到上打印二叉树
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型vector<vector<>>
*/
vector<vector<int> > levelOrderBottom(TreeNode* root) {
// write code here
if(root==NULL)
return {};
vector<vector<int>>ans;
int now_level=0;//如果要输出当前遍历到的层次，这个才有用，本题无用。
int len =1;//记录当前层次节点的个数
int next =0;//记录下一层加入节点的个数
queue<TreeNode*>qu;
qu.push(root);
while(true){
vector<int>n;
while(len)
{
TreeNode* first = qu.front();
n.push_back(first->val);
qu.pop();
if(first->left!=NULL)
{
qu.push(first->left);
next++;
}
if(first->right!=NULL)
{
qu.push(first->right);
next++;
}
len--;
}
ans.push_back(n);
len =next;
next =0;
now_level++;
if(len ==0)
break;
}
vector<vector<int>>ans2;//数组反转，也可用vector自带的reverse进行数组反转。
for(int i=ans.size()-1;i>=0;i--)
{
ans2.push_back(ans[i]);
}
return ans2;
}
};
发表于 2022-03-19 15:04:54
回复(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整型二维数组
*/
public int[][] levelOrderBottom (TreeNode root) {
// write code here
Stack<int[]> stack = new Stack<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int queueSize = queue.size();
int[] layer = new int[queueSize];
for(int i = 0; i < queueSize; i++){
TreeNode node = queue.poll();
layer[i] = node.val;
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
}
stack.push(layer);
}
int row = 0;
int[][] res = new int[stack.size()][];
while(!stack.isEmpty()){
res[row] = stack.pop();
row ++;
}
return res;
}
}
发表于 2021-12-12 20:23:39
回复(0)
层序遍历结果入栈，最后弹栈即可，我用的 ArrayDeque, 也可使用 LinkedList, 性能差别不大
public static int[][] levelOrderBottom(TreeNode root) {
// write code here
Deque<TreeNode> deque = new ArrayDeque<>();
Stack<int[]> resStack = new Stack<>();
deque.add(root);
while (!deque.isEmpty()) {
int size = deque.size();
int[] currLayer = new int[size];
for (int i = 0; i < size; i++) {
TreeNode curr = deque.poll();
assert curr != null;
currLayer[i] = curr.val;
if (curr.left != null) deque.add(curr.left);
if (curr.right != null) deque.add(curr.right);
}
resStack.push(currLayer);
}
int[][] res = new int[resStack.size()][];
for (int i = 0; i < res.length; i++)
res[i] = resStack.pop();
return res;
}
发表于 2024-11-06 22:04:42
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
/**
* NC224 从下到上打印二叉树
* @author d3y1
*/
public class Solution {
private int[][] results;
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 程序入口
*
* @param root TreeNode类
* @return int整型二维数组
*/
public int[][] levelOrderBottom (TreeNode root) {
// return solution1(root);
// return solution2(root);
// return solution3(root);
// return solution4(root);
return solution44(root);
}
///////////////////////////////////////////////////////////////////////////////////
private ArrayList<QueueNode> levelNodes = new ArrayList<>();
private class QueueNode {
TreeNode node;
int level;
int seq;
public QueueNode(TreeNode node, int level, int seq){
this.node = node;
this.level = level;
this.seq = seq;
}
}
/**
* bfs + sort
* @param root
* @return
*/
private int[][] solution1(TreeNode root){
Queue<QueueNode> queue = new LinkedList<>();
int level = 0;
int seq = 1;
queue.offer(new QueueNode(root, level, seq));
QueueNode queueNode;
int size = 0;
int[] width = new int[1000];
while(!queue.isEmpty()){
size = queue.size();
// width = Math.max(width, size);
width[level] = size;
level++;
while(size-- > 0){
queueNode = queue.poll();
levelNodes.add(queueNode);
if(queueNode.node.left != null){
queue.offer(new QueueNode(queueNode.node.left, level, seq++));
}
if(queueNode.node.right != null){
queue.offer(new QueueNode(queueNode.node.right, level, seq++));
}
}
}
Collections.sort(levelNodes, (o1, o2) -> {
if(o1.level == o2.level){
return o1.seq-o2.seq;
}else{
return o2.level-o1.level;
}
});
results = new int[level][];
for(int i=0; i<level; i++){
results[i] = new int[width[level-i-1]];
}
int lastLevel = -1;
int currLevel;
int index = 0;
for(QueueNode qNode: levelNodes){
currLevel = qNode.level;
if(currLevel != lastLevel){
index = 0;
}
results[level-currLevel-1][index++] = qNode.node.val;
lastLevel = currLevel;
}
return results;
}
///////////////////////////////////////////////////////////////////////////////////
/**
* bfs
* @param root
* @return
*/
private int[][] solution2(TreeNode root){
LinkedList<int[]> list = new LinkedList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int[] level;
TreeNode currNode;
while (!queue.isEmpty()) {
int levelSize = queue.size();
level = new int[levelSize];
for (int i = 0; i < levelSize; i++) {
currNode = queue.poll();
if (currNode.left != null){
queue.offer(currNode.left);
}
if (currNode.right != null){
queue.offer(currNode.right);
}
level[i] = currNode.val;
}
list.add(level);
}
Iterator<int[]> dIterator = list.descendingIterator();
results = new int[list.size()][];
int i = 0;
while (dIterator.hasNext()) {
results[i++] = dIterator.next();
}
return results;
}
///////////////////////////////////////////////////////////////////////////////////
private class Node {
TreeNode treeNode;
int level;
public Node(TreeNode treeNode, int level){
this.treeNode = treeNode;
this.level = level;
}
}
/**
* bfs
* @param root
* @return
*/
private int[][] solution3(TreeNode root){
if(root == null){
return new int[][]{};
}
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
Queue<Node> queue = new LinkedList<>();
queue.offer(new Node(root, 0));
Node node;
int preLevel = 0;
ArrayList<Integer> levelList = new ArrayList<>();
while(!queue.isEmpty()){
node = queue.poll();
if(node.treeNode.left != null){
queue.offer(new Node(node.treeNode.left, node.level+1));
}
if(node.treeNode.right != null){
queue.offer(new Node(node.treeNode.right, node.level+1));
}
if(node.level != preLevel){
list.add(levelList);
levelList = new ArrayList<>();
}
levelList.add(node.treeNode.val);
preLevel = node.level;
}
list.add(levelList);
results = new int[list.size()][];
int width;
for(int i=0; i<list.size(); i++){
width = list.get(list.size()-i-1).size();
results[i] = new int[width];
for(int j=0; j<width; j++){
results[i][j] = list.get(list.size()-i-1).get(j);
}
}
return results;
}
///////////////////////////////////////////////////////////////////////////////////
/**
* bfs
* @param root
* @return
*/
private int[][] solution4(TreeNode root){
if(root == null){
return new int[][]{};
}
ArrayList<int[]> list = new ArrayList<int[]>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int size;
int[] level;
TreeNode node;
while(!queue.isEmpty()){
size = queue.size();
level = new int[size];
for(int i=0; i<size; i++){
node = queue.poll();
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
level[i] = node.val;
}
list.add(level);
}
results = new int[list.size()][];
int width;
for(int i=0; i<list.size(); i++){
width = list.get(list.size()-i-1).length;
results[i] = new int[width];
for(int j=0; j<width; j++){
results[i][j] = list.get(list.size()-i-1)[j];
}
}
return results;
}
///////////////////////////////////////////////////////////////////////////////////
/**
* bfs
* @param root
* @return
*/
private int[][] solution44(TreeNode root){
if(root == null){
return new int[][]{};
}
ArrayList<int[]> list = new ArrayList<int[]>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int size;
int[] level;
TreeNode node;
while(!queue.isEmpty()){
size = queue.size();
level = new int[size];
for(int i=0; i<size; i++){
node = queue.poll();
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
level[i] = node.val;
}
list.add(0, level);
}
results = new int[list.size()][];
for(int i=0; i<list.size(); i++){
results[i] = list.get(i);
}
return results;
}
}
发表于 2025-01-17 13:05:44
回复(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整型二维数组
*/
public int[][] levelOrderBottom (TreeNode root) {
// write code here
if(root == null){
return new int[0][0];
}
//定义一个队列存放每一层的节点
Queue<TreeNode> queue = new LinkedList<>();
//定义数组列表存储遍历的结果
LinkedList<int[]> list = new LinkedList<>();
//添加根节点
queue.offer(root);
//层序遍历
while(!queue.isEmpty()){
//定义数组存储每一层的节点个数
int[] nums = new int[queue.size()];
for(int i = 0; i < nums.length; i++){
//获取并删除队首元素，访问它的左右子树,依次将左右子树放入队列中
TreeNode node = queue.poll();
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
nums[i] = node.val;
}
list.add(nums);
}
int[][] ans = new int[list.size()][];
for(int j = 0; j < list.size(); j++){
ans[j] = list.get(list.size() - 1 - j);
}
return ans;
}
}
发表于 2024-05-14 22:16:44
回复(0)
# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param root TreeNode类 # @return int整型二维数组 # class Solution: def levelOrderBottom(self , root: TreeNode) -> List[List[int]]: # write code here res = [] q = [] q.append(root) while len(q) != 0: next_q = [] tmp = [] for node in q: tmp.append(node.val) if node.left is not None: next_q.append(node.left) if node.right is not None: next_q.append(node.right) res.append(tmp) q = next_q return res[::-1]
发表于 2024-04-21 12:04:26
回复(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整型二维数组
*/
public int[][] levelOrderBottom (TreeNode root) {
// write code here
//创建队列用来遍历节点
Queue<TreeNode> queue = new LinkedList<>();
//栈保存层序遍历结果
Stack<ArrayList<Integer>> stack = new Stack<>();
queue.add(root);
//层序遍历
while (!queue.isEmpty()) {
int size = queue.size();
//将当层遍历结果保存到栈
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < size; 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);
}
}
stack.add(list);
}
//将栈中结果保存到listAll
ArrayList<ArrayList<Integer>> listAll = new ArrayList<>();
while (!stack.isEmpty()) {
listAll.add(stack.pop());
}
//创建数组赋值
int arr[][] = new int[listAll.size()][];
for (int i = 0; i < listAll.size(); i++) {
arr[i]=new int[listAll.get(i).size()];
for (int j = 0; j < listAll.get(i).size(); j++) {
arr[i][j] = listAll.get(i).get(j);
}
}
return arr;
}
}
发表于 2023-05-17 15:37:38
回复(0)
package main
import _"fmt"
import . "nc_tools"
/*
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型二维数组
*/
func levelOrderBottom( root *TreeNode ) [][]int {
ans:=[][]int{[]int{root.Val}}
q:=[]*TreeNode{root}
for len(q)>0{
new_q:=[]*TreeNode{}
vals:=[]int{}
for _,qi:=range q{
if qi.Left!=nil{
new_q=append(new_q,qi.Left)
vals=append(vals,qi.Left.Val)
}
if qi.Right!=nil{
new_q=append(new_q,qi.Right)
vals=append(vals,qi.Right.Val)
}
}
if len(vals)>0{
ans=append([][]int{vals},ans...)
}
q=new_q
}
return ans
}
发表于 2023-03-07 23:47:06
回复(0)
先层序遍历再翻转数组即可
vector<vector<int> > levelOrderBottom(TreeNode* root) {
//write your codevector<vector<int>> res;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
vector<int> temp;
while (size--) {
TreeNode* cur = q.front();
q.pop();
temp.push_back(cur->val);
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
if (!temp.empty()) res.push_back(temp);
}
reverse(res.begin(), res.end());
return res;
}
发表于 2022-08-15 17:58:39
回复(0)
vector<vector<int> > levelOrderBottom(TreeNode* root) {
// write code here
//层序遍历，然后reverse
vector<vector<int>> rt;
vector<int> cur;
if(!root)
{
return rt;
}
queue<TreeNode*> qe;
qe.push(root);
while(!qe.empty())
{
int size=qe.size();
cur.clear();
for(int i=0;i<size;i++)
{
auto tmp=qe.front();
qe.pop();
cur.push_back(tmp->val);
if(tmp->left)
qe.push(tmp->left);
if(tmp->right)
qe.push(tmp->right);
}
rt.push_back(cur);
}
reverse(rt.begin(),rt.end());
return rt;
}
发表于 2022-06-30 15:58:50
回复(0)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型vector<vector<>>
*/
vector<vector<int> > levelOrderBottom(TreeNode* root) {
// write code here
vector<vector<int>> ans;
if(!root) return ans;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()){
vector<int> t;
for(int i=que.size()-1;i>=0;i--){
auto node=que.front();
t.push_back(node->val);
que.pop();
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
}
ans.push_back(t);
}
reverse(ans.begin(),ans.end());
return ans;
}
};
发表于 2022-02-28 12:17:06
回复(0)
class Solution: def levelOrderBottom(self , root: TreeNode) -> List[List[int]]: # write code here q=[root] all_res=[] while q: size=len(q) res=[] while size>0: cur=q.pop(0) res.append(cur.val) if cur.left: q.append(cur.left) if cur.right: q.append(cur.right) size-=1 all_res.append(res) return all_res[::-1]
发表于 2022-01-19 07:07:38
回复(0)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型vector<vector<>>
*/
vector<vector<int> > levelOrderBottom(TreeNode* root) {
// write code here
stack<vector<int>>cmp;
vector<vector<int>>tmp;
if(!root)return tmp;
queue<TreeNode*>Myqueue;
Myqueue.push(root);
while(!Myqueue.empty())
{
vector<int>hmp;
int n=Myqueue.size();
for(int i=0;i<n;i++)
{
TreeNode* head=Myqueue.front();
Myqueue.pop();
if(head->left)Myqueue.push(head->left);
if(head->right)Myqueue.push(head->right);
hmp.push_back(head->val);
}
cmp.push(hmp);
//tmp.push_back(hmp);
}
int h=cmp.size();
for(int i=0;i<h;i++)
{
tmp.push_back(cmp.top());
cmp.pop();
}
return tmp;
}
};
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型vector<vector<>>
*/
vector<vector<int> > levelOrderBottom(TreeNode* root) {
// write code here
stack<vector<int>>cmp;
vector<vector<int>>tmp;
if(!root)return tmp;
queue<TreeNode*>Myqueue;
Myqueue.push(root);
while(!Myqueue.empty())
{
vector<int>hmp;
int n=Myqueue.size();
for(int i=0;i<n;i++)
{
TreeNode* head=Myqueue.front();
Myqueue.pop();
if(head->left)Myqueue.push(head->left);
if(head->right)Myqueue.push(head->right);
hmp.push_back(head->val);
}
cmp.push(hmp);
//tmp.push_back(hmp);
}
int h=cmp.size();
for(int i=0;i<h;i++)
{
tmp.push_back(cmp.top());
cmp.pop();
}
return tmp;
}
};
发表于 2021-12-21 07:35:29
回复(0)
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型二维数组
*/
public int[][] levelOrderBottom (TreeNode root) {
// write code here
Deque<TreeNode> q = new LinkedList<>();
ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
q.offer(root);
TreeNode cur;
int size;
while(!q.isEmpty()){
size = q.size();
ArrayList<Integer> list = new ArrayList<>();
for(int i=0;i<size;i++){
cur = q.poll();
list.add(cur.val);
if(cur.left!=null) q.offer(cur.left);
if(cur.right!=null) q.offer(cur.right);
}
ans.add(list);
}
int[][] res = new int[ans.size()][];
for(int i=0;i<ans.size();i++){
ArrayList<Integer> l = ans.get(i);
res[ans.size()-1-i] = new int[l.size()];
for(int j=0;j<l.size();j++){
res[ans.size()-1-i][j] = l.get(j);
}
}
return res;
}
}
发表于 2021-12-03 22:33:03
回复(0)
先层序遍历，再翻转数组即可
func levelOrderBottom( root *TreeNode ) (result [][]int) {
var dfs func(*TreeNode, int)
dfs = func(node *TreeNode, level int) {
if node == nil {return}
if len(result) == level {
result = append(result, []int{})
}
result[level] = append(result[level], node.Val)
dfs(node.Left, level+1)
dfs(node.Right, level+1)
}
dfs(root, 0)
//翻转数组
for l, r := 0, len(result)-1; l < r; {
result[l], result[r] = result[r], result[l]
l++; r--
}
return
}
发表于 2021-11-26 16:07:07
回复(0)
问题信息
难度：
15条回答
25收藏
3245浏览
通过挑战的用户
查看代码-
2023-02-27 16:45:15
-
2022-09-19 17:35:36
-
2022-09-15 10:50:27 -
2022-09-14 01:11:58
-
2022-09-12 11:45:02
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
