【JZOF】77 Print binary tree in zigzag

题目描述：

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

解法：

1. The first solution uses theJDK的Collections.reverse,Reverse the collection.Do not use this tool if asked during the interview,则需要换一种写法.

public class LeftRightReverseOrder {
    
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
    
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(pRoot);
        boolean reverse = false;
        while (!queue.isEmpty()) {
    
            ArrayList<Integer> list = new ArrayList<>();
            int cnt = queue.size();
            while (cnt-- > 0) {
    
                TreeNode node = queue.poll();
                if (node == null)
                    continue;
                list.add(node.val);
                queue.add(node.left);
                queue.add(node.right);
            }
            if (reverse)
                Collections.reverse(list);
            reverse = !reverse;
            if (list.size() != 0)
                ret.add(list);
        }
        return ret;
    }

}

2. 第二种解法：

Do it in two stacks.
stack1Store odd-numbered layer nodes,The child nodes of the odd-numbered layer nodes are in the order of left and rightpush到stack2.
slack2Store even-numbered layer nodes.The child nodes of even-numbered nodes are in right-left orderpush到stack1.

public class Solution {
    
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
    
        ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >();

        if (pRoot == null) {
    
            return res;
        }
        // 奇数层
        Stack<TreeNode> s1 = new Stack<>();
        // 偶数层
        Stack<TreeNode> s2 = new Stack<>();
        s1.push(pRoot);

        while (!s1.isEmpty() || !s2.isEmpty()) {
    
            ArrayList<Integer> row = new ArrayList<>();
            if (!s1.isEmpty()) {
    
                while (!s1.isEmpty()) {
    
                    TreeNode node = s1.pop();
                    row.add(node.val);
                    if (node.left != null) {
    
                        s2.push(node.left);
                    }
                    if (node.right != null) {
    
                        s2.push(node.right);
                    }
                }
            } else {
    
                while (!s2.isEmpty()) {
    
                    TreeNode node = s2.pop();
                    row.add(node.val);
                    if (node.right != null) {
    
                        s1.push(node.right);
                    }
                    if (node.left != null) {
    
                        s1.push(node.left);
                    }
                }
            }
            res.add(row);
        }

        return res;
    }

}