题目地址：二叉树的层序遍历 II

解题思路

本文解题思路来自左程云老师算法课新手班第七节

题目要求返回的是链表套链表 ,而且是倒序。不妨先考虑正序输出

正序输出也就是另一道leetCode的题 二叉树的层序遍历

假设有这么一颗树

正序返回就是[[1],[2,3],[4,5,6,7],[8,9,10]]。

我们可以考虑使用队列来解决

定义一个队列queue，首先将root传入队列，

Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);

当前queue内有一个节点，进行一次如下操作，先将该节点弹出到一个链表内，如果左支不为空，就将左支塞入队列，右支不为空也塞入队列，现在queue内是[2,3]。正好为第二层。

现在queue内有两个节点，执行两次上述操作，那么现在也会出现一个链表为[2,3]，那么进行两次操作，

弹出2，2的左支塞入队列，现在queue为[3,4]，2 的右支塞入队列，为[3,4,5]。第一次操作结束。弹出3，依然左支，右支塞入，现在queue为 [4,5,6,7]。

 while (!queue.isEmpty()) {
    int size = queue.size();
    List<Integer> curAns = new LinkedList<>();
    for (int i = 0; i < size; i++) {
        TreeNode curNode = queue.poll();
        curAns.add(curNode.val);
        if (curNode.left != null) {
             queue.add(curNode.left);
        }
        if (curNode.right != null) {
            queue.add(curNode.right);
        }
    }
}

所以现在只有将这些链表逆序输出的过程了

我们可以在循环外面定义一个List<List<Integer>>。在内部循环结束时，使用add方法。去在0位置插入每一个生成的链表那么最后生成的最深层就是会返回的头。

ans.add(0, curAns);

返回对象的选择 ArrayList or LinkedList

那么就需要看看是使用ArrayList还是使用LinkedList

可以通过一个小测试，去看一看那种更优

使用这个System.currentTimeMillis();，在循环前后就可以得出该循环的用时。

    public static void main(String[] args) {
        int TestTime = 10000;
        long start;
        long end;
        ArrayList<Integer> list1 = new ArrayList<>();
        start = System.currentTimeMillis();
        for (int i = 0;i<TestTime;i++){
            list1.add(0,i);
        }
        end  = System.currentTimeMillis();
        System.out.println(end - start);
        LinkedList<Integer> list2 = new LinkedList<>();
        start = System.currentTimeMillis();
        for (int i = 0;i<TestTime;i++){
            list2.add(0,i);
        }
        end  = System.currentTimeMillis();
        System.out.println(end - start);
    }

当TestTime为1 0000时，对比结果为4：1

当TestTime为10 0000时，对比结果为344：2

当TestTime为100 0000时，对比结果为14 3158：151

对比已经很明显。LinkedList的效率明显优于ArrayList。所以我们选用LinkedList做为我们的返回对象

List<List<Integer>> ans = new LinkedList<>();

完整代码

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