【JZOF】77按之字形打印二叉树

题目描述：

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

解法：

1. 第一种解法借助了JDK的Collections.reverse，将集合逆序。如果面试时候要求不许用这个工具类，则需要换一种写法。

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. 第二种解法：

采用两个栈的方式来做。
stack1存放奇数层节点，奇数层节点的子节点按照左右的顺序push到stack2。
slack2存放偶数层节点。偶数层节点的子节点按照右左的顺序push到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;
    }

}