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

package AC;
import java.util.*;
public class NC14按之字形顺序打印二叉树 {
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
}

public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
    int status=1;//奇数从左到右，偶数从右到左，每遍历一层，则加一
    ArrayList<ArrayList<Integer> > res=new ArrayList<>();//存放结果
    //Queue<TreeNode> q=new LinkedList<>();
    Stack<TreeNode> s=new Stack<>();//存奇数层节点
    Stack<TreeNode> ss=new Stack<>();//存偶数层节点
    if(pRoot==null){//这一段没想到
       return res;

    }
    s.add(pRoot);
    while (!s.isEmpty() || !ss.isEmpty()){
        ArrayList<Integer> temp=new ArrayList<>();//存放当前层的结果
        if(status%2==1){
            int n=s.size();
            for(int i=0;i<n;i++){
                TreeNode node=s.pop();
                if(node.left!=null)ss.add(node.left);
                if(node.right!=null)ss.add(node.right);
                temp.add(node.val);
            }
        }
        else{
            int nn=ss.size();
            for(int i=0;i<nn;i++){
                TreeNode node=ss.pop();
                if(node.right!=null)s.add(node.right);
                if(node.left!=null)s.add(node.left);
                temp.add(node.val);
            }

        }
        status++;
        res.add(temp);
    }
    return res;
}

}