LC103: Binary Tree Zigzag Level Order Traversal

Posted on In

Previously

This problem is the more complex version of LC102: Binary Tree Level Order Traversel. In the previous version, we can only use a Queue to implement a FIFO order traversal to solve the problem:

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
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }

        List<List<Integer>> ans = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            List<Integer> lst = new ArrayList<>();
            int size = queue.size();    // store how many nodes in each level
            while (size > 0) {
                TreeNode curr = queue.poll();
                lst.add(curr.val);
                if (curr.left != null) {
                    queue.add(curr.left);
                }
                if (curr.right != null) {
                    queue.add(curr.right);
                }
                size--;
            }
            ans.add(lst);
        }
        return ans;
    }
}

// time: O(n)
// space: O(n) (O(k) actually, k is for the most amount of nodes in each level, worst case n)

Solution

For this problem where the zigzag traverse is required, we have 2 ways to solve it, either retrieve the nodes in a reversed order when level is odd (0 is the first level) or retrieve the node normally but reverse the list. It turns out that both can be done in the same time complexity. What’s more, the first method can be implemented in 2 different ways as well.

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
37
38
39
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }

        List<List<Integer>> ans = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean oddLevel = false; // 0 is first level

        while (!queue.isEmpty()) {
            List<Integer> lst = new LinkedList<>();
            int size = queue.size();
            while (size > 0) {
                TreeNode curr = queue.poll();
                if (oddLevel) {
                    lst.addFirst(curr.val);
                } else {
                    lst.add(curr.val); // default add is addLast
                }

                if (curr.left != null) {
                    queue.add(curr.left);
                }
                if (curr.right != null) {
                    queue.add(curr.right);
                }
                size--;
            }
            ans.add(lst);
            oddLevel = !oddLevel;
        }
        return ans;
    }
}

// time: O(n)
// space: O(n) (O(k) actually, same idea with above)

Here we can also use the Collections.reverse(List<E> list) to reverse the List, but the time complexity for the reverse would be O(n) which will cause the total time to be O(n^2).

Takeaways

  • LinkedList has method addFirst(E) and addLast(E) with default add(E) is addLast(E) and the time complexity both are O(n).
  • In Java, we can’t directly get the node object if we are provided List<E> lst no matter it’s linkedlist or arraylist.
  • Collections.reverse(List<E> list) time complexity is O(n).