牛客网：二叉树的之字形层序遍历

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
例如：
给定的二叉树是{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);
    }
}