题目描述

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

image

由题意我们可以知道，打印结果应该为：

A

C、B

D、E、F、G

我们可以先将第一行A保存在一个数据容器中；

然后根据第一行依次得到第二行C、B并将其放入一个数组容器；

根据第二行得到第三行D、E、F、G时先得到的为D，而D为B的子节点，B在第二行是最后放入的却最先被第三行使用，这种后入先出的特点正好符合栈的特点。

于是我们可以使用两个栈来分别保存第奇数行和第偶数行。

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        //第奇数行，里面顺序为从左向右
        Stack<TreeNode> stackLeft = new Stack<TreeNode>();
        Stack<TreeNode> stackRight = new Stack<TreeNode>();
        ArrayList<Integer> newLine = new ArrayList<Integer>();
        TreeNode current = null;
        if(pRoot == null) {
            return res;
        }
        //第偶数行，里面顺序为从右向左
        newLine.add(pRoot.val);
        res.add(newLine);
        stackLeft.push(pRoot);
        while(!(stackLeft.isEmpty() && stackRight.isEmpty())) {
                //遍历奇数行
            if(!stackLeft.isEmpty()) {
                newLine = new ArrayList<Integer>();
                while(!stackLeft.isEmpty()) {
                    current = stackLeft.pop();
                    if(current.right != null) {
                        stackRight.push(current.right);
                        newLine.add(current.right.val);
                    }
                    if(current.left != null) {
                        stackRight.push(current.left);
                        newLine.add(current.left.val);
                    }
                }
                if(newLine.size() != 0) {
                    res.add(newLine);
                }
            }
                //遍历偶数行
            if(!stackRight.isEmpty()) {
                newLine = new ArrayList<Integer>();
                while(!stackRight.isEmpty()) {
                    current = stackRight.pop();
                    if(current.left != null) {
                        stackLeft.push(current.left);
                        newLine.add(current.left.val);
                    }
                    if(current.right != null) {
                        stackLeft.push(current.right);
                        newLine.add(current.right.val);
                    }
                }
                if(newLine.size() != 0) {
                    res.add(newLine);
                }
            }   
        }
        return res;
    }
}

解法二：

使用队列，今天懒得写了，之后补上