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

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;

    }

}
*/
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
//         偶数行 奇数行 两个
        ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
        Stack<TreeNode>st1 = new Stack<TreeNode>();
        Stack<TreeNode>st2 = new Stack<TreeNode>();
        if(pRoot!=null)st1.add(pRoot);
        ArrayList<Integer> list = null;
        while(!st1.empty() || !st2.empty()){
            list = new ArrayList<Integer>();
            while(!st1.empty()){
                TreeNode t = st1.pop();
                list.add(t.val);
                if(t.left!=null) st2.add(t.left);
                if(t.right!=null) st2.add(t.right);

            }
            if(list.size()>0) ans.add(list);
            list = new ArrayList<Integer>();
            while(!st2.empty()){
                TreeNode t = st2.pop();
                list.add(t.val);
                if(t.right!=null) st1.add(t.right);
                if(t.left!=null) st1.add(t.left);
            }
            if(list.size()>0) ans.add(list);
        }
        return ans;
    }

}

思路来源：题解 由于每一层顺序不一样，因此考虑奇偶层各设置一个栈