# 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;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://shuati.gitbook.io/crack-lintcode/linkedin/binary-tree-zigzag-level-order-traversal.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.