# 103. Binary Tree Zigzag Level Order Traversal

## problem description

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]
]
```

## algorithm thought

zigzag层次遍历，分析之后得知，可以用两个栈来辅助遍历。参差遍历本来是用一个队列就行。但是这个用两个栈，然后定义一个bool变量指定现在是左到右还是右到左，分别用一个栈辅助遍历。最后处理方式和层次遍历一样

使用两个栈的方法肯定还有优化的地方，去看了discuss之后，发现可以直接使用一个队列来做。最后遍历的结果需保存在一个vector中，我们默认只能push\_back但是其实可以先定义好vector，最后看情况从左右分别将结果放置进去。

## code

```cpp
//use two stack 
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        stack<TreeNode*> q1,q2;
        vector<vector<int>> res;
        if(root==NULL)
            return res;
        bool bo=true;
        q1.push(root);
        while(true){
            if(bo){
                vector<int> ve;
                while(!q1.empty()){
                    TreeNode* tmp=q1.top();
                    q1.pop();
                    if(tmp==NULL)
                        break;
                    ve.push_back(tmp->val);
                    if(tmp->left)
                        q2.push(tmp->left);
                    if(tmp->right)
                        q2.push(tmp->right);
                }
                res.push_back(ve);
                bo=false;
                if(q2.empty())
                    break;
            }
            else{
                vector<int> ve;
                while(!q2.empty()){
                    TreeNode* tmp=q2.top();
                    q2.pop();
                    if(tmp==NULL)
                        break;
                    ve.push_back(tmp->val);
                    if(tmp->right)
                        q1.push(tmp->right);
                    if(tmp->left)
                        q1.push(tmp->left);
                }
                res.push_back(ve);
                bo=true;
                if(q1.empty())
                    break;
            } 
        }
        return res;
    }
};


//use one queue
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        vector<vector<int>> res;
        if(root==NULL)
            return res;
        bool leftToRight=true;
        TreeNode* tmp = new TreeNode(-1);
        q.push(root);q.push(tmp);
        vector<int> ve(1);
        int i=0;
        while(true){
            TreeNode* t=q.front();
            q.pop();
            if(t==tmp){
                res.push_back(ve);
                ve.clear();
                ve.resize(q.size());
                if(q.empty())
                    break;
                q.push(tmp);
                leftToRight=!leftToRight;
                i=0;
                continue;
            }
            if(t->left)
                q.push(t->left);
            if(t->right)
                q.push(t->right);
            if(leftToRight){
                ve[i]=t->val;
            }else{
                ve[ve.size()-i-1]=t->val;
            }
            i++;
        }
        return res;
    }
};
```

## algorithm analysis

遍历问题时间复杂度还是一样的，都是O(n)


---

# 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://kongchengzhuge.gitbook.io/leetcode/103.-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.