103. 二叉树的锯齿形层次遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res=new ArrayList<>();//假设根节点在第0层，偶数层从左向右
        Stack<TreeNode> evenLevel = new Stack<>();//记录偶数层的节点栈
		Stack<TreeNode> oddLevel = new Stack<>();//记录奇数层的节点栈
        if(root==null) return res;
        evenLevel.push(root);
        for(int i=0;!evenLevel.isEmpty()||!oddLevel.isEmpty();i++)
        {
            res.add(new ArrayList<Integer>());
            if(i%2==0)//如果是偶数层，下一层奇数层该从右往左遍历了，因为栈是先入后出，所以应该先入栈每个节点的左子节点
            {
                while(!evenLevel.isEmpty())
                {
                    TreeNode t=evenLevel.pop();
                    res.get(i).add(t.val);
                    if(t.left!=null) oddLevel.push(t.left);
                    if(t.right!=null) oddLevel.push(t.right);


                }
            }
            else
            {
                while(!oddLevel.isEmpty())//这是奇数层，下一层是偶数层，所以说要先入栈右子树
                {
                    TreeNode t=oddLevel.pop();
                    res.get(i).add(t.val);
                     if(t.right!=null) evenLevel.push(t.right);
                    if(t.left!=null) evenLevel.push(t.left);//这里判断条件写反了，卡了好久

                }
            }

        }
        return res;

    }
}