103. Binary Tree Zigzag Level Order Traversal

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],

    3
   / 
  9  20
    /  
   15   7

return its zigzag level order traversal as:

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

这道题就是在level order traverse的基础上变了一点，这点可以通过Collections.reverse()方法来实现。

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> results = new ArrayList<>();
        if(root == null) return results;
        rec(root, 0, results);
        for(int i = 0; i < results.size(); i++){
            if(i % 2 == 1){
                Collections.reverse(results.get(i));
            }
        }
         return results;
    }
    public void rec(TreeNode root, int height,  List<List<Integer>> list){
        if(root == null) return;
        if(height == list.size()){
            list.add(new ArrayList());
        }
        list.get(height).add(root.val);
        rec(root.left, height + 1, list);
        rec(root.right, height + 1, list);
    }
}

然后还有一种稍微简单点的方法，设置一个boolean来检查从左到右还是从右到左，后者的话，调用ArrayList.add(0, val)来保证每次进来的值都在第一个，就实现了倒着加进去。

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> results = new ArrayList<>();
        if(root == null) return results;
        rec(root, 0, results, true);
         return results;
    }
    public void rec(TreeNode root, int height,  List<List<Integer>> list, boolean isleftright){
        if(root == null) return;
        if(height == list.size()){
            list.add(new ArrayList());
        }
        if(isleftright){
        list.get(height).add(root.val);
        }
        else
            list.get(height).add(0,root.val);
        rec(root.left, height + 1, list, !isleftright);
        rec(root.right, height + 1, list, !isleftright);
    }
}