老实人解法

分析题目可以知道，奇数行总是从左到右，偶数行总是从右到左
初步想法就是bfs！
如何从右边到左遍历的同时能够使下一行能够从左到右遍历呢？
可以用栈， 依次从右到左 放子树 放左 右
使用栈存储下一行数据（奇数行总是从左到右，偶数行总是从右到左）
奇数行：扫描当前行存入ArrayList，依次放入每个结点的 左 右 左 右，下一行（偶数行） 栈出栈就是 右 左 右 左
偶数行：扫描当前行存入ArrayList，依次放入每个结点的 右 左 右 左，下一行（奇数行） 栈出栈就是 左 右 左 右
每遍历完成一行存入result

public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (pRoot == null) {
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        // 使用一个flag来标记是奇数行还是偶数行 奇数行为true，偶数行为false
        boolean flag = true;
        stack.push(pRoot);
        while (stack.size() != 0) {
            ArrayList<Integer> curList = new ArrayList<>();
            ArrayList<TreeNode> curLine = new ArrayList<>();
            while (stack.size() != 0) {
                curLine.add(stack.pop());
            }
            if (flag) {
                for (TreeNode node : curLine) {
                    curList.add(node.val);
                    // 奇数行下一行，先放左后放右
                    if (node.left != null) {
                        stack.push(node.left);
                    }
                    if (node.right != null) {
                        stack.push(node.right);
                    }
                }
            } else {
                for (TreeNode node : curLine) {
                    curList.add(node.val);
                    // 偶数行下一行，先放右后放左
                    if (node.right != null) {
                        stack.push(node.right);
                    }
                    if (node.left != null) {
                        stack.push(node.left);
                    }
                }
            }
            result.add(curList);
            flag = !flag;
        }
        return result;
    }