【双栈法，beat 99 %】 | #按之字形顺序打印二叉树#

思路：

利用栈后入先出的特性，一个栈保存当前层节点，一个栈保存下一层节点。入栈规则如下：

• 当前层为奇数层时：下一层为从左到右输出，故从右到左入栈即可。
• 当前层为偶数层时：下一层为从右到左输出，故从左到右入栈即可。

代码：

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>(); // 总结果
        ArrayList<Integer> layerRes; // 每层的结果
        if(pRoot == null) return res;

        Stack<TreeNode> curLayer = new Stack<>(); // 当前层节点
        Stack<TreeNode> nextLayer;// 下一层节点
        curLayer.push(pRoot);
        int nLayer = 0;
        while(!curLayer.empty()){
            nLayer++;
            int size = curLayer.size();
            layerRes = new ArrayList<>();
            nextLayer = new Stack<>(); // 重置nextLayer
            while(size-- > 0){
                TreeNode tempNode = curLayer.pop();
                layerRes.add(tempNode.val);
                if(nLayer % 2 == 0){ // 偶数层：下一层为从左到右输出，故从右到左入栈即可
                    if(tempNode.right != null) nextLayer.push(tempNode.right);
                    if(tempNode.left != null) nextLayer.push(tempNode.left);
                }else{ //奇数层：下一层为从右到左输出，故从左到右入栈即可
                    if(tempNode.left != null) nextLayer.push(tempNode.left);
                    if(tempNode.right != null) nextLayer.push(tempNode.right);
                }
            }
            curLayer = nextLayer; // 更新下一层
            res.add(layerRes);
        }
        return res;
    }
}