# 二叉树的锯齿形层序遍历

<p>给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。</p>

<p>例如：<br />
给定二叉树 <code>[3,9,20,null,null,15,7]</code>,</p>

<pre>
    3
   / \
  9  20
    /  \
   15   7
</pre>

<p>返回锯齿形层序遍历如下：</p>

<pre>
[
  [3],
  [20,9],
  [15,7]
]
</pre>

<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
```

### after

```cpp

```

## 答案

```cpp
class Solution
{
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode *root)
    {
        vector<vector<int>> result;
        if (root == NULL)
        {
            return result;
        }
        deque<TreeNode *> node_queue;
        node_queue.push_back(root);
        node_queue.push_back(NULL);

        deque<int> level_list;
        bool is_order_left = true;

        while (node_queue.size() > 0)
        {
            TreeNode *curr_node = node_queue.front();
            node_queue.pop_front();
            if (curr_node != NULL)
            {
                if (curr_node->left != NULL)
                {
                    node_queue.push_back(curr_node->left);
                }
                if (curr_node->right != NULL)
                {
                    node_queue.push_back(curr_node->right);
                }
            }
            else
            {
                vector<int> tmp;
                for (int a : level_list)
                {
                    tmp.push_back(a);
                }
                result.push_back(tmp);
                level_list.clear();
                if (node_queue.size() > 0)
                {
                    node_queue.push_back(NULL);
                }
                is_order_left = !is_order_left;
            }
        }
        return result;
    }
};
```
## 选项

### A

```cpp
class Solution
{
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode *root)
    {
        if (root == NULL)
            return {};

        vector<vector<int>> res;
        int flag = 1;
        stack<TreeNode *> a, b;
        a.push(root);
        while (!a.empty() || !b.empty())
        {
            vector<int> cur;
            while (flag == 1 && !a.empty())
            {
                root = a.top();
                cur.push_back(root->val);
                a.pop();
                if (root->left != NULL)
                    b.push(root->left);
                if (root->right != NULL)
                    b.push(root->right);
            }
            while (flag == -1 && !b.empty())
            {
                root = b.top();
                cur.push_back(root->val);
                b.pop();
                if (root->right != NULL)
                    a.push(root->right);
                if (root->left != NULL)
                    a.push(root->left);
            }
            flag = -1 * flag;
            res.push_back(cur);
        }
        return res;
    }
};
```

### B

```cpp
class Solution
{
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode *root)
    {

        vector<vector<int>> ans;
        if (!root)
            return ans;
        queue<TreeNode *> qnode;
        bool orderByLeft = true;

        qnode.push(root);

        while (!qnode.empty())
        {
            int levelSize = qnode.size();
            deque<int> level;

            for (int i = 0; i < levelSize; i++)
            {
                auto curNode = qnode.front();
                qnode.pop();

                if (orderByLeft)
                {
                    level.push_back(curNode->val);
                }
                else
                {
                    level.push_front(curNode->val);
                }

                if (curNode->left != NULL)
                    qnode.push(curNode->left);
                if (curNode->right != NULL)
                    qnode.push(curNode->right);
            }
            orderByLeft = !orderByLeft;
            vector<int> curlevel{level.begin(), level.end()};
            ans.push_back(curlevel);
        }
        return ans;
    }
};
```

### C

```cpp
class Solution
{
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode *root)
    {
        if (!root)
            return {};
        vector<vector<int>> res;
        queue<TreeNode *> q{{root}};
        int cnt = 0;
        while (!q.empty())
        {
            vector<int> oneLevel;
            for (int i = q.size(); i > 0; i--)
            {
                TreeNode *t = q.front();
                q.pop();
                oneLevel.push_back(t->val);
                if (t->left)
                    q.push(t->left);
                if (t->right)
                    q.push(t->right);
            }
            if (cnt % 2 == 1)
                reverse(oneLevel.begin(), oneLevel.end());
            res.push_back(oneLevel);
            cnt++;
        }
        return res;
    }
};
```

### D
```cpp
class Solution
{
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode *root)
    {
        vector<vector<int>> results;
        if (root == NULL)
        {
            return results;
        }
        zigzagLevelOrderDFS_helper(root, 0, results);
        return results;
    }

    void zigzagLevelOrderDFS_helper(TreeNode *node, int level, vector<vector<int>> &results)
    {
        if (level >= results.size())
        {
            vector<int> new_level;
            new_level.push_back(node->val);
            results.push_back(new_level);
        }
        else
        {
            if (level % 2 == 0)
            {
                results[level].push_back(node->val);
            }
            else
            {
                results[level].insert(results[level].begin(), node->val);
            }
        }
        if (node->left != NULL)
        {
            zigzagLevelOrderDFS_helper(node->left, level + 1, results);
        }
        if (node->right != NULL)
        {
            zigzagLevelOrderDFS_helper(node->right, level + 1, results);
        }
    }
};
```