给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
例如：
给定的二叉树是{3,9,20,#,#,15,7},
image
该二叉树之字形层序遍历的结果是
[
[3],
[20,9],
[15,7]
]
重要的事情说三遍: 之 型遍历
思路: 二叉树层次遍历的变形题，可以用 dfs 进行层次遍历，当 拿到偶数层的时候，需要将元素 进行反转 存储。
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) {
// write code here
ArrayList<ArrayList<Integer>> result = new ArrayList<> ();
if(root == null){
return result;
}
dfs(root,result,1);
return result;
}
private void dfs(TreeNode root,ArrayList<ArrayList<Integer>> res,int height){
if(root == null){
return;
}
// 如果 height 大于 res.size(), 说明 说明这一层没有对应的集合，需要新创建
if(height > res.size()){
res.add(new ArrayList<>());
}
if(height%2 != 0){
// 奇数层，直接存放
res.get(height-1).add(root.val);
}else{
//偶数层，需要将拿到的数进行反存储
res.get(height-1).add(0,root.val);
}
//对左子树进行遍历
dfs(root.left,res,height +1);
//对右子树进行遍历
dfs(root.right,res,height +1);
}
}
