Binary Tree Zigzag Level Order Traversal

Q:
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,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

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

A:
这道题面试的时候，要说。 有2种思路。  dfs 或者bfs
如果bfs的话，就是每层打印。 那么有2种方法，   递归  或者 迭代。


---------------------3rd pass-------- DFS ---------------

public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> all = new ArrayList<List<Integer>>();
        int height = getHeight(root);
        for(int i =0;i<height;i++){
            all.add(new ArrayList<Integer>());
        }
        dfs(all,root,0);
        return all;
    }
    private void dfs(List<List<Integer>> all, TreeNode root, int level){
        if(root == null)
            return;
        if(level %2==0){
            all.get(level).add(root.val);
        }else{
            all.get(level).add(0,root.val);
        }
            dfs(all,root.left,level+1);
            dfs(all,root.right,level+1);
    }
    private int getHeight(TreeNode root){
        if(root == null)
            return 0;
        else
            return 1+Math.max(getHeight(root.left),getHeight(root.right));
    }
}

--------------------------1 st pass-----------------------
就是把 “Binary Tree Level Order Traversal ” 问题里的一句
普通的level order traversal，只不过每层的时候，按照flag，加入结果的位置不同 而已

public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        if(root == null)
            return res;
        List<TreeNode> parentLevel = new LinkedList<>();
        parentLevel.add(root);
        boolean isLeft2Right = true;
        while(parentLevel.isEmpty()==false){
            List<TreeNode> newParentLevel = new LinkedList<>();
            List<Integer> tmpRes = new LinkedList<>();
            while( ! parentLevel.isEmpty()){
                TreeNode node = parentLevel.remove(0);
                if(isLeft2Right)
                    tmpRes.add(node.val);
                else
                    tmpRes.add(0,node.val);
                if(node.left != null)
                    newParentLevel.add(node.left);
                if(node.right!=null)
                    newParentLevel.add(node.right);
            }
            isLeft2Right = !isLeft2Right;
            parentLevel = newParentLevel;
            res.add(tmpRes);
        }
        return res;
    }
}

Mistakes: