[LeetCode] 103. Binary Tree Zigzag Level Order Traversal

Posted on | In

Problem

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example: Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

1
2
3
4
5
[
  [3],
  [20,9],
  [15,7]
]

Explanation 1

  1. Similar to 102. Binary Tree Level Order Traversal, but this time we need to add value from left to right, in the next level, we add values from right to left. Then next level, add values from left to right, next level from right to left.

  2. When the current level is from left to right, we can normally pop value from the beginning and add its child to the end (left child first). When the current level is from right to left, we pop values from the end and add its child (right child first) to the beginning.

Solution 1

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
40
41
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;

        LinkedList<TreeNode> q = new LinkedList<>();
        q.offer(root);

        boolean leftToRight = true;

        while (!q.isEmpty()) {
            List<Integer> temp = new ArrayList<>();
            for (int i = q.size()-1; i >= 0; i--) {
                TreeNode pop;
                if (leftToRight) {
                    pop = q.remove(0);
                    if (pop.left != null) q.add(pop.left);
                    if (pop.right != null) q.add(pop.right);
                } else {
                    pop = q.remove(q.size()-1);
                    if (pop.right != null) q.add(0, pop.right);
                    if (pop.left != null) q.add(0, pop.left);
                }
                temp.add(pop.val);
            }
            res.add(temp);
            leftToRight = !leftToRight;
        }

        return res;
    }
}

Explanation 2

  1. We can also use DFS to solve this problem. Start from level 0, if the current level is even number, then we add the current root value to the end of sublist res[level], else add it to the front of the sublist res[level].

Solution 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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    void helper(TreeNode root, int level, List<List<Integer>> res) {
        if (root == null) return;
        if (res.size() == level) res.add(new ArrayList<>());
        if (level % 2 == 0) {
            res.get(level).add(root.val);
        } else {
            res.get(level).add(0, root.val);
        }
        helper(root.left, level+1, res);
        helper(root.right, level+1, res);
    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        helper(root, 0, res);
        return res;
    }
}