剑指 Offer 32 - III. 从上到下打印二叉树 III

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。


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

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：
[
  [3],
  [20,9],
  [15,7]
]
 

提示：
节点总数 <= 1000

思路

在逐层打印的基础上加一个index%2；

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
private static class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        ArrayDeque<TreeNode> arrayDeque = new ArrayDeque<>();
        List<List<Integer>> result = new ArrayList<>();
        arrayDeque.add(root);
        int index = 0;

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

            for (int i = 0; i < size; i++) {
                TreeNode cur = arrayDeque.poll();
                if (index % 2 == 0) {
                    temp.add(cur.val);
                } else {
                    temp.addFirst(cur.val);
                }

                if (cur.left != null) {
                    arrayDeque.add(cur.left);
                }
                if (cur.right != null) {
                    arrayDeque.add(cur.right);
                }

            }
            result.add(temp);
            index++;
        }
        return result;
    }
}