107.二叉树的层序遍历II

1.题目

给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其自底向上的层序遍历为：

[
  [15,7],
  [9,20],
  [3]
]

2.思路

很郁闷，我本着先刷简单题的，然后发现102与107是一样的，只是一个正序一个倒序，正序是中等题，倒序就是简单题……

看着答案代码给捋一下思路：大概意思就是，先定义一个链表，然后从头节点开始插入到这个列表中，如果左树、右树不为null，则将左树、右树插入到链表中；插入链表中后，将左树、右树节点的值插入到结果集中，遍历完成后返回这个结果集：

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> levelOrder = new LinkedList<List<Integer>>();
        if (root == null) {
            return levelOrder;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                TreeNode left = node.left, right = node.right;
                if (left != null) {
                    queue.offer(left);
                }
                if (right != null) {
                    queue.offer(right);
                }
            }
            levelOrder.add(0, level);
        }
        return levelOrder;
    }