题目描述

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

题解

用两个栈实现，一个栈stackToRight用于保存需要从左往右打印的节点，另一个栈stackToLeft用于保存下一层需要从右往左打印的节点。

由题意，第一行按照从左到右的顺序打印，因此把根节点加入stackToRight中。然后循环开始，当stackToRight不为空时，则把其下一层的节点添加到stackToLeft中（注意左右子节点添加的顺序）；当stackToLeft不为空时，则把其下一层的节点添加到stackToRight中（注意左右子节点添加的顺序）。与此同时，使用list记录打印的节点。当两个栈都为空时循环结束。

public ArrayList<ArrayList<Integer>> Print(TreeNode root) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    Stack<TreeNode> stackToRight = new Stack<>();
    Stack<TreeNode> stackToLeft = new Stack<>();
    if (root == null)
        return res;

    stackToRight.push(root);
    while (!stackToRight.isEmpty() || !stackToLeft.isEmpty()) {
        if (!stackToRight.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<>();
            while (!stackToRight.isEmpty()){
                TreeNode p = stackToRight.pop();
                list.add(p.val);
                if (p.left != null)
                    stackToLeft.push(p.left);
                if (p.right != null)
                    stackToLeft.push(p.right);
            }
            res.add(list);
        }
        if (!stackToLeft.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<>();
            while (!stackToLeft.isEmpty()){
                TreeNode p = stackToLeft.pop();
                list.add(p.val);
                if (p.right != null)
                    stackToRight.push(p.right);
                if (p.left != null)
                    stackToRight.push(p.left);
            }
            res.add(list);
        }
    }
    return res;
}