题目描述

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

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

返回其层次遍历结果:

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

题解

双端队列

经过前两道题的分析, 我们已经可以操控每一层的节点了, 这道题延伸出来的是层数的奇偶问题, 如果奇数层正序摆放, 偶数层逆序摆放.

既然经过上一道题每一层的层数我们已经记录下来了, 那就只剩摆放的问题了.

将每一层打印的数用双端队列存储, 那么每遍历到一层时只需要判断该层的奇偶性然后采用头部添加还是尾部添加就好了.

public List<List<Integer>> levelOrder(TreeNode root) {

    List<List<Integer>> res = new ArrayList<>();
    if (root == null)
        return res;

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

    while (!queue.isEmpty()) {
        LinkedList<Integer> temp = new LinkedList<>();
        int level_length = queue.size();

        for (int i = 0; i < level_length; i++) {
            TreeNode node = queue.poll();
            if (level % 2 == 0) temp.addLast(node.val);
            else temp.addFirst(node.val);

            if (node.left != null)
                queue.add(node.left);
            if (node.right != null)
                queue.add(node.right);
        }
        res.add(temp);
        level++;
    }

    return res;
}