7.15 第一次做，无法 AC
7.16 一次 AC

题目描述

原题链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/

解题思路

K 神题解：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/solution/

• 出队列是用 Queue；保存是用 LinkedList；所以不存在我所想的那种顾虑！！！！傻逼呀我！

7.16 思路：

• 这题其实和 32 II. 差不多。

• 遍历的时候都是一层一层从左到右的遍历，没有变，只不过是加入结果集的顺序不同，第1层和下面所有的基数层都是正序的输出，所以结果集就正常的后入进去就行了；而偶数层就从结果集的头插进去就行了，最后就可以是倒序的了。

  class Solution {  
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            LinkedList<Integer> list = new LinkedList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode tmp = queue.poll();
                if(tmp.left != null) queue.add(tmp.left);
                if(tmp.right != null) queue.add(tmp.right);
                if(res.size() % 2 == 0) list.addLast(tmp.val); // 第0层算偶数层，正常从队列尾部插入
                else list.addFirst(tmp.val);
            }
            res.add(list);
        }
        return res;
    }
  }