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

 /**
     * 题目描述
     * 请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
     * 示例1
     * 输入
     * {8,6,10,5,7,9,11}
     * 返回值
     * [[8],[10,6],[5,7,9,11]]
     */

public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> datas = new ArrayList<>();
        if (pRoot == null) {
            return datas;
        }

        //奇数行从左到右,偶数行从右到左
        //奇数栈
        Stack<TreeNode> oddStack = new Stack<>();
        //偶数栈
        Stack<TreeNode> evenStack = new Stack<>();
        oddStack.add(pRoot);

        //当前需要遍历的是奇数栈
        boolean isOdd = true;

        while (!oddStack.isEmpty() || !evenStack.isEmpty()) {
            ArrayList<Integer> item = new ArrayList<>();
            if (isOdd) {
                while (!oddStack.isEmpty()) {
                    final TreeNode poll = oddStack.pop();
                    item.add(poll.val);
                    if (poll.left != null) {
                        evenStack.push(poll.left);
                    }
                    if (poll.right != null) {
                        evenStack.push(poll.right);
                    }
                }
            } else {
                while (!evenStack.isEmpty()) {
                    while (!evenStack.isEmpty()) {
                        final TreeNode poll = evenStack.pop();
                        item.add(poll.val);
                        if (poll.right != null) {
                            oddStack.add(poll.right);
                        }

                        if (poll.left != null) {
                            oddStack.add(poll.left);
                        }
                    }
                }
            }
            isOdd = !isOdd;
            datas.add(item);
            continue;
        }

        return datas;
    }