题解 | #按之字形顺序打印二叉树#

import java.util.ArrayList;
import java.util.Stack;

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

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

    }

}
*/
//1.将节点放入st1
//3.打印st1中节点，将其孩子节点放入st2（从左到右）
//4.打印st2中节点，将其孩子节点放入st1（从右到左）
//5.重复上述过程，直到栈空为止
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        Stack<TreeNode> st1 = new Stack<TreeNode>();
        Stack<TreeNode> st2 = new Stack<TreeNode>();
        // ArrayList<Integer> layer = new ArrayList<Integer>();
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        TreeNode temp;
        if(pRoot == null){
            return result;
        }
        st1.push(pRoot);
        while(!st1.empty()||!st2.empty()){
            ArrayList<Integer> layer1 = new ArrayList<Integer>();
            while(!st1.empty()){
                temp = st1.pop();
                if(temp.left != null){
                    st2.push(temp.left);
                }
                if(temp.right != null){
                    st2.push(temp.right);
                }
                layer1.add(temp.val);
            }
            if(!layer1.isEmpty()){
                result.add(layer1);
            }
            ArrayList<Integer> layer2 = new ArrayList<Integer>();
            while(!st2.empty()){
                temp = st2.pop();
                if(temp.right != null){
                    st1.push(temp.right);
                }
                if(temp.left != null){
                    st1.push(temp.left);
                }
                layer2.add(temp.val);
            }
            if(!layer2.isEmpty()){
                result.add(layer2);
            }
        }
        return result;

    } 


}