leetcode 103 Binary Tree Zigzag Level Order Traversal
z
 2019-04-09 10:36:27  

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]
]
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
import utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class BinaryTreeZigzagLevelOrderTraversa {
  public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    helper(ans, root, 0);
    return ans;

  }

  public void helper(List<List<Integer>> ans, TreeNode root, int level) {
    if (root == null) return ;
    if (ans.size() == level) {
      ans.add(new ArrayList<>());
    }
    List<Integer> t = ans.get(level);
    if (level % 2 == 0) {
      t.add(root.val);
    }
    else
      t.add(t.size()-1, root.val);

    helper(ans, root.left, level+1);
    helper(ans, root.right, level+1);

  }

}