题解 | #从下到上打印二叉树#

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[][] result;
    private ArrayList<QueueNode> levelNodes = new ArrayList<>();

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 程序入口
     *
     * @param root TreeNode类
     * @return int整型二维数组
     */
    public int[][] levelOrderBottom (TreeNode root) {
        // return solution1(root);
        return solution2(root);
    }

    /**
     * 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;
            }
        });

        result = new int[level][];
        for(int i=0; i<level; i++){
            result[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;
            }
            result[level-currLevel-1][index++] = qNode.node.val;
            lastLevel = currLevel;
        }

        return result;
    }

    /**
     * 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();
        result = new int[list.size()][];
        int i = 0;
        while (dIterator.hasNext()) {
            result[i++] = dIterator.next();
        }
        return result;
    }

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