【32.3】按之字形顺序打印二叉树

题目描述

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

分析：两个堆

    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
        if (pRoot == null) return arrayLists;
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        
        int flag = 1;
        stack1.push(pRoot);

        while (!stack1.empty() || !stack2.empty()) {
            ArrayList<Integer> array = new ArrayList<>();
            int size = 0;
            if ((flag & 1) == 1) {
                size = stack1.size();
                for (int i = 0; i < size; i++) {
                    TreeNode temp = stack1.pop();
                    array.add(temp.val);
                    if (temp.left != null) {
                        stack2.push(temp.left);
                    }
                    if (temp.right != null) {
                        stack2.push(temp.right);
                    }
                }
            } else {
                size = stack2.size();
                for (int i = 0; i < size; i++) {
                    TreeNode temp = stack2.pop();
                    array.add(temp.val);
                    if (temp.right != null) {
                        stack1.push(temp.right);
                    }
                    if (temp.left != null) {
                        stack1.push(temp.left);
                    }
                }
            }
            flag++;
            arrayLists.add(array);
        }
        return arrayLists;
    }