【剑指Offer】按之字形顺序打印二叉树

题目

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

实现

public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    
    public TreeNode(int val) {
        this.val = val;
    }
}

public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
    ArrayList<ArrayList<Integer>> results = new ArrayList<>();

    if (pRoot != null) {
        Stack<TreeNode>[] stack = (Stack<TreeNode>[]) new Stack[2];

        for (int i = 0; i < 2; i++)
            stack[i] = new Stack<>();
        
        int idx = 0;
        stack[idx].push(pRoot);

        while (!stack[idx].isEmpty()) {
            ArrayList<Integer> result = new ArrayList<>();
            int start = 0;
            int end = stack[idx].size();

            while (start++ < end){
                TreeNode node = stack[idx].pop();
                result.add(node.val);

                if (idx == 0) {
                    if (node.left != null)
                        stack[1-idx].push(node.left);

                    if (node.right != null)
                        stack[1-idx].push(node.right);
                }
                else {
                    if (node.right != null)
                        stack[1-idx].push(node.right);

                    if (node.left != null)
                        stack[1-idx].push(node.left);
                }
            }

            idx = 1 - idx;
            results.add(result);
        }
    }

    return results;
}