15 binary-tree-zigzag-level-order

题目描述

给定一个二叉树，返回该二叉树的之字形层序遍历，（从左向右，下一层从右向左，一直这样交替）
例如：
给定的二叉树是{3,9,20,#,#,15,7},
3↵ / ↵ 9 20↵ / ↵ 15 7
该二叉树之字形层序遍历的结果是
[↵ [3],↵ [20,9],↵ [15,7]↵]

代码

思路：就是层次遍历

public ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        if(root==null)
            return list;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        boolean flag = true;
        while(!q.isEmpty()) {
            int size = q.size();
            ArrayList<Integer> arr = new ArrayList<Integer>();
            for(int i=0;i<size;i++) {
                TreeNode node = q.poll();
                if(flag) {
                    arr.add(node.val);                        
                }else {
                    arr.add(0,node.val);
                }
                if(node.left!=null)
                    q.add(node.left);
                if(node.right!=null)
                    q.add(node.right);
            }
            list.add(arr);
            flag = !flag;
        }        
        return list;