image.png

    思路：对于这种指定遍历顺序的问题，引入头尾两个位置标记，和一个方向标记，
    难点在于

    • 头节点尾节点的确定，需要分从左到右和从右到左的方式。
    • 下一层节点入遍历的顺序用队列是无法实现的，这里选择了用辅助栈。

    当然最简单的方案是先不管顺序，按照层次遍历拿到各行的值，然后该逆序的逆序。
    其他解法有用双端队列的，要看一下
    奥，双短队列也是在阶段阶段逆序的，不过用了一个巧妙的关系
    当到达当前层结尾时，队列的长度为下一层的节点个数。

    1. class Solution {
    2.     public List<List<Integer>> levelOrder(TreeNode root) {
    3.         Queue<TreeNode> queue = new LinkedList<>();
    4.         List<List<Integer>> res = new ArrayList<>();
    5.         if(root != null) queue.add(root);
    6.         while(!queue.isEmpty()) {
    7.             LinkedList<Integer> tmp = new LinkedList<>();
    8.             for(int i = queue.size(); i > 0; i--) {
    9.                 TreeNode node = queue.poll();
    10.                 if(res.size() % 2 == 0) tmp.addLast(node.val); // 偶数层 -> 队列头部
    11.                 else tmp.addFirst(node.val); // 奇数层 -> 队列尾部
    12.                 if(node.left != null) queue.add(node.left);
    13.                 if(node.right != null) queue.add(node.right);
    14.             }
    15.             res.add(tmp);
    16.         }
    17.         return res;
    18.     }
    19. }
    21. 作者：jyd
    22. 链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/solution/mian-shi-ti-32-iii-cong-shang-dao-xia-da-yin-er--3/
    23. 来源：力扣（LeetCode）
    24. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

    tips : java中Collection.reverse 可以直接对结合逆序。

    1. class Solution {
    2.     public List<List<Integer>> levelOrder(TreeNode root) {
    3.         Queue<TreeNode> queue = new LinkedList<>();
    4.         List<List<Integer>> res = new ArrayList<>();
    5.         if(root != null) queue.add(root);
    6.         while(!queue.isEmpty()) {
    7.             List<Integer> tmp = new ArrayList<>();
    8.             for(int i = queue.size(); i > 0; i--) {
    9.                 TreeNode node = queue.poll();
    10.                 tmp.add(node.val);
    11.                 if(node.left != null) queue.add(node.left);
    12.                 if(node.right != null) queue.add(node.right);
    13.             }
    14.             if(res.size() % 2 == 1) Collections.reverse(tmp);
    15.             res.add(tmp);
    16.         }
    17.         return res;
    18.     }
    19. }
    21. 作者：jyd
    22. 链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/solution/mian-shi-ti-32-iii-cong-shang-dao-xia-da-yin-er--3/
    23. 来源：力扣（LeetCode）
    24. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。