给定一棵二叉树,返回齐自底向上的层序遍历。
数据范围:二叉树上节点数满足 ,二叉树上的值满足
样例图:
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; } };
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; } }
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; } }
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 }
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; }
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; } };
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]
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; } }
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 }