给定一棵二叉树，返回齐自底向上的层序遍历。
数据范围：二叉树上节点数满足 
，二叉树上的值满足 
样例图：
[编程题]从下到上打印二叉树
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
//创建队列用来遍历节点
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)
用栈接住层次遍历每一层的一维数组结果，然后再弹栈形成最终要返回的二维数组结果
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)
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)
问题信息
难度：
4条回答
25收藏
3253浏览
通过挑战的用户
查看代码-
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号
