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]

]

思路：与二叉树水平序解题思路几乎相同，得到水平序结果之后。再对偶数链表反转就可以。‘

代码例如以下：

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

public class Solution {

    List<List<Integer>> list = new ArrayList<List<Integer>>();

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

        dfs(0,root);

        //每隔1行交换顺序

        for(int i = 1; i < list.size(); i = i+2){

        	List<Integer> al = list.get(i);

        	int len = al.size();

        	//倒序交换

        	for(int j = 0; j + j < len-1; j++){

        		int k = al.get(j);

        		al.set(j, al.get(len-1-j));

        		al.set(len-1-j, k);

        	}

        }

        return list;

    }

    /**

     * 中序遍历，依据深度加入list

     * @param dep 树的深度

     * @param root 根节点

     */

    private void dfs(int dep,TreeNode root){

    	if(root == null){

            return;

        }

        List<Integer> al;//依据情况得到al值

        if(list.size() > dep){

            al = list.get(dep);

        }else{

            al = new ArrayList<Integer>();

            list.add(al);

        }

        dfs(dep+1,root.left);

        al.add(root.val);

        dfs(dep+1,root.right);

    }

}