JZ77 按之字形顺序打印二叉树

描述

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

数据范围：0 \le n \le 15000≤n≤1500,树上每个节点的val满足 |val| <= 1500∣val∣<=1500
要求：空间复杂度：O(n)，时间复杂度：O(n)

例如：
给定的二叉树是{1,2,3,#,#,4,5}

该二叉树之字形层序遍历的结果是

[[1],[3,2],[4,5]];

思路（双向链表 + 二维顺序表）：实际上，如果你理解了这种方法，那么用队列来做也是一样的道理；建立一个双向链表，开始时先放入根节点，相当于记录第一层的顺序，之后每次将一行的顺序放入顺序表顺序或者逆序打印（根据题目要求），如何放入一行呢？先用记录下链表的长度（每行的长度）每次用一个key值存放并删除链表的头节点，再放入左右孩子（此操作执行的次数根据链表的长度而定，也就是每一行的长度），再链表不为空的前提下，循环以上操作即可

达到的效果如下图（如何得到每一行的数据）：

代码如下： 

    public ArrayList<ArrayList<Integer> > Print(TreeNode root) {
        ArrayList<ArrayList<Integer>> retArray = new ArrayList<>();
        if(root == null){
            return retArray;
        }
        List<TreeNode> list = new LinkedList<>();
        //负责确定奇数还是偶数
        int count = 1;
        list.add(root);
        while(!list.isEmpty()){
            ArrayList<Integer> array = new ArrayList<>();
            //如果是奇数，每次从左往右入顺序表
            if(count % 2 != 0){
                for(int start = 0; start < list.size(); start++){
                    array.add(list.get(start).val);
                }
            }else{//偶数从右往左
                for(int end = list.size() - 1; end >= 0; end--){
                    array.add(list.get(end).val);
                }
            }
            //输入后入二维顺序表
            ArrayList<Integer> tmpArray = new ArrayList<>(array);
            retArray.add(tmpArray);
            //每次都删除零下标位置
            int tmp = 0;
            int row = list.size();
            while(!list.isEmpty() && tmp < row){
                TreeNode key = list.remove(0);
                //将key的左右结点放入链表
                if(key.left != null){
                    list.add(key.left);
                }
                if(key.right != null){
                    list.add(key.right);
                }
                tmp++;
            }
            //去下一行
            count++;
        }
        return retArray;
    }

    public ArrayList<ArrayList<Integer> > Print(TreeNode root) {
        ArrayList<ArrayList<Integer>> retArray = new ArrayList<>();
        if(root == null){
            return retArray;
        }
        List<TreeNode> list = new LinkedList<>();
        //负责确定奇数还是偶数
        int count = 1;
        list.add(root);
        while(!list.isEmpty()){
            ArrayList<Integer> array = new ArrayList<>();
            //如果是奇数，每次从左往右入顺序表
            if(count % 2 != 0){
                for(int start = 0; start < list.size(); start++){
                    array.add(list.get(start).val);
                }
            }else{//偶数从右往左
                for(int end = list.size() - 1; end >= 0; end--){
                    array.add(list.get(end).val);
                }
            }
            //输入后入二维顺序表
            ArrayList<Integer> tmpArray = new ArrayList<>(array);
            retArray.add(tmpArray);
            //每次都删除零下标位置
            int tmp = 0;
            int row = list.size();
            while(!list.isEmpty() && tmp < row){
                TreeNode key = list.remove(0);
                //将key的左右结点放入链表
                if(key.left != null){
                    list.add(key.left);
                }
                if(key.right != null){
                    list.add(key.right);
                }
                tmp++;
            }
            //去下一行
            count++;
        }
        return retArray;
    }