首页 > 试题广场 >

从下到上打印二叉树

[编程题]从下到上打印二叉树

热度指数：1544 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一棵二叉树，返回齐自底向上的层序遍历。

数据范围：二叉树上节点数满足 $1 \le n \le 1000 \$ ，二叉树上的值满足 $|val| \le 10^9 \$

样例图：

示例1

输入

{1,2,3,4,#,5,6}

输出

[[4,5,6],[2,3],[1]]

说明

如题面图示

示例2

输入

{1,2}

输出

[[2],[1]]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

C++

牛客503684343号

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)

Java

pein531

用栈接住层次遍历每一层的一维数组结果，然后再弹栈形成最终要返回的二维数组结果

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)

Java

梁山教父

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)

C++

你一点都不可爱

先层序遍历再翻转数组即可

vector<vector<int> > levelOrderBottom(TreeNode* root) {

//write your code
vector<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)

C++

牛客487629784号

    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)

C++

wydxry

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)

Python 3

Joy_9

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)

C++

QNBZ

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;
}
};

发表于 2021-12-21 07:35:29 回复(0)

Java

Fireflies_Wu

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)

王飞-6

先层序遍历，再翻转数组即可

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)