题目描述

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

实现方法

1. 不同于普通的分层打印，这个需要从左到右和从右到左的方式交替进行，
那么我们就不能使用队列实现这个结果。
2. 从左到右和从右到左其实就是一个存储的方向问题，那么我们可以使用两个栈
交替存储实现,因为栈的后进先出的特性刚好可以实现这个交替打印的实现。
3. 具体实现过程：根据栈后进先出的特性，如果我们要从左到右打印，那么用一个名为rightT
oLeftStore的栈存储这一行，然后逐个取出打印就是从左向右，从右向左打印同理用一个名为l
eftToRightStore的栈进行处理
4. 打印的过程我们可以采用一个level控制，level=0表示打印奇数层，level=1表示打印偶数
层，然后将对应的存储栈数据取出，过程和分层遍历一样。
5. 但是在取出数据后，需要注意的是存储栈的左右子节点需要根据层的奇偶性判断，奇数节点
是从左往右存储在rightToLeftStore（奇数栈）中，从右往左的数据存储在leftToRightStore
（偶数栈）中，那么我们取出奇数层节点，其子节点就要按照先存储左子节点，再存储右子节
点到偶数栈中。类似的，从右往左打印时，子节点要按照先存储右子节点、再存储左子节点到奇数栈中实现。

java源码

import java.util.ArrayList;
import java.util.*;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (pRoot == null) return result;
        ArrayList<Integer> temp = new ArrayList<>();
        Stack<TreeNode> leftToRightStore = new Stack<>();
        Stack<TreeNode> rightToLeftStore = new Stack<>();
        int level = 0;
        rightToLeftStore.push(pRoot);
        while (!leftToRightStore.isEmpty() || !rightToLeftStore.isEmpty()) {
            if (level == 0) {
                //奇数层打印,从左往右
                TreeNode current = rightToLeftStore.pop();
                temp.add(current.val);
                if (current.left != null) leftToRightStore.push(current.left);
                if (current.right != null) leftToRightStore.push(current.right);
                //判定这一层是否打印完，即栈空
                if (rightToLeftStore.isEmpty()) {
                    level = 1;
                    result.add(new ArrayList(temp));
                    temp.clear();
                }
            } else {
                //偶数层打印
                TreeNode current = leftToRightStore.pop();
                temp.add(current.val);
                if (current.right != null) rightToLeftStore.push(current.right);
                if (current.left != null) rightToLeftStore.push(current.left);
                //判定这一层是否打印完，即栈空
                if (leftToRightStore.isEmpty()) {
                    level = 0;
                    result.add(new ArrayList(temp));
                    temp.clear();
                }
            }
        }
        return result;
    }

}

附上分层打印代码

import java.util.ArrayList;
import java.util.*;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (pRoot == null) return result;
        ArrayList<Integer> temp = new ArrayList<>();
        int toBePrint = 1;
        int nextLevel = 0;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(pRoot);
        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            temp.add(current.val);
            toBePrint--;
            if (current.left != null) {
                queue.add(current.left);
                nextLevel++;
            }
            if (current.right != null) {
                queue.add(current.right);
                nextLevel++;
            }
            if (toBePrint == 0) {
                result.add(new ArrayList(temp));
                temp.clear();
                toBePrint = nextLevel;
                nextLevel = 0;
            }
        }
        return result;
    }
    
}