按之字形顺序打印二叉树

描述

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

例如：

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

思路

用栈实现，考察二叉树的层次遍历。用两个栈分别存放奇数层和偶数层的节点，当奇数层栈弹出节点的时候将该节点的左、右节点先后压入偶数层的栈中，一直循环直至奇数层栈没有节点。再从偶数层栈中弹出节点，将该节点的右、左节点先后压入奇数层栈中，循环直至偶数层栈没有节点。反复循环直至所有节点都弹出，则遍历完所有节点。

    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        //创建目标数组
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        //安全性检测
        if (pRoot == null) {
            return list;
        }
        //奇数层栈，从左向右
        Stack<TreeNode> left = new Stack<>();
        //偶数层栈，从右向左
        Stack<TreeNode> right = new Stack<>();
        //奇数层栈中放入根节点
        left.push(pRoot);
        //遍历两个栈直至两个栈都为空，则输出完毕。
        while (!left.isEmpty() || !right.isEmpty()) {
            //当奇数层栈非空时
            if (!left.isEmpty()) {
                //创建层次数组
                ArrayList<Integer> arrayList = new ArrayList<>();
                //遍历奇数层栈直至为空
                while (!left.isEmpty()) {
                    //弹出栈得到当前节点
                    TreeNode node = left.pop();
                    //判断该节点的左节点是否为空
                    if (node.left!=null) {
                        //将该节点的左节点加入到右链表中。
                        right.push(node.left);
                    }
                    //判断该节点的右节点是否为空
                    if (node.right!=null) {
                        //将该节点的右节点加入到右链表中。
                        right.push(node.right);
                    }
                    //向层次数组中加入该节点的值
                    arrayList.add(node.val);
                }
                //向目标数组加入层次数组
                list.add(arrayList);
            }
            //当偶数层栈非空时
            if (!right.isEmpty()) {
                //创建层次数组
                ArrayList<Integer> arrayList = new ArrayList<>();
                //遍历偶数层栈直至为空
                while (!right.isEmpty()) {
                    //弹出栈得到当前节点
                    TreeNode node = right.pop();
                    //判断该节点的右节点是否为空
                    if (node.right!=null) {
                        //将该节点的右节点加入到右链表中。
                        left.push(node.right);        
                    }
                    //判断该节点的左节点是否为空
                    if (node.left!=null) {
                        //将该节点的左节点加入到右链表中。
                        left.push(node.left);
                    }
                    //向层次数组中加入该节点的值
                    arrayList.add(node.val);
                }
                //向目标数组加入层次数组
                list.add(arrayList);
            }
        }
        return list;
    }

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }