首页 > 试题广场 >

从下到上打印二叉树

[编程题]从下到上打印二叉树
  • 热度指数:1869 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一棵二叉树,返回齐自底向上的层序遍历。

数据范围:二叉树上节点数满足 ,二叉树上的值满足

样例图:

示例1

输入

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

输出

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

说明

如题面图示 
示例2

输入

{1,2}

输出

[[2],[1]]

说明:本题目包含复杂数据结构TreeNode,点此查看相关信息
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)