题解 | #按之字形顺序打印二叉树#

/**
     * 简单暴力解法
     * 用双端队列好
     * addFirst
     * addLast
     *
     * @param pRoot
     * @return
     */
    public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        LinkedList<TreeNode> queue = new LinkedList<>(); // 每层往后存，从头取
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        if (pRoot == null) {
            return ret;
        }
        queue.offer(pRoot);
        int m = 1;
        while (queue.peek() != null) {
            ArrayList<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                if (m % 2 == 0) {
                    stack.push(node);
                } else {
                    level.add(node.val);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            if (m % 2 == 0) {
                while (stack.size() != 0) {
                    level.add(stack.pop().val);
                }
            }
            ret.add(level);
            m++;
        }
        return ret;
    }