> For the complete documentation index, see [llms.txt](https://shuati.gitbook.io/crack-lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://shuati.gitbook.io/crack-lintcode/linkedin/binary-tree-zigzag-level-order-traversal.md).

# Binary Tree Zigzag Level Order Traversal

每次往res里放list的时候，要check一下list是不是空，因为很有可能树遍历完以后，有一个stack是空的，那么对应的list就是空的，空的list不能加到最后的接过去

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:\
Given binary tree `[3,9,20,null,null,15,7]`,<br>

```
    3
   / \
  9  20
    /  \
   15   7
```

return its zigzag level order traversal as:<br>

```
[
  [3],
  [20,9],
  [15,7]
]
```

用两个栈维护正序和反序输出，s1往s2push 的时候，左先进，右后进，这样在遍历s2时，就先遍历后进去的，输出的顺序就是倒着的层序遍历，s2往s1 push的时候，右先进，左后进，这样遍历的时候就是从左到右的正常循序，

2个坑：

1. 用同一个list的话，往res里传的时候应该deep copy
2. 往res里传的时候应该保证list不为空，因为两个stack的循环都在一个大循环里，有时候期中一个stack为空

时间复杂度 o(n) , space o(n)

```java
/**
 * 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<>();
        
        if(root == null)
            return res;
        
        Stack<TreeNode> s1 = new Stack<>();
        
        Stack<TreeNode> s2 = new Stack<>();
        
        s1.push(root);
        
        while(!s1.isEmpty() || !s2.isEmpty()){
            List<Integer> list = new ArrayList<>();
            while(!s1.isEmpty()){
                TreeNode node = s1.pop();
                list.add(node.val);
                //先进左，后进右，右先出，左后出
                if(node.left != null) s2.push(node.left);
                if(node.right != null) s2.push(node.right);
            }
            if(!list.isEmpty())
                res.add(new ArrayList<>(list));
            list.clear();
            
            while(!s2.isEmpty()){
                TreeNode node = s2.pop();
                
                list.add(node.val);
                //右先进，左后进，左先出，右后出
                if(node.right != null) s1.push(node.right);
                if(node.left != null) s1.push(node.left);
            }
            if(!list.isEmpty())
                res.add(new ArrayList<>(list));
            list.clear();

        }
        
        return res;
    }
}
```