leecode/problems/103.binary-tree-zigzag-level-order-traversal.md

## 题目地址
https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/

## 题目描述
和leetcode 102 基本是一样的，思路是完全一样的。

```
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],
    3
   / \
  9  20
    /  \
   15   7
return its zigzag level order traversal as:
[
  [3],
  [20,9],
  [15,7]
]
```

## 思路

这道题可以借助`队列`实现，首先把root入队，然后入队一个特殊元素Null(来表示每层的结束)。


然后就是while(queue.length), 每次处理一个节点，都将其子节点（在这里是left和right）放到队列中。

然后不断的出队， 如果出队的是null，则表式这一层已经结束了，我们就继续push一个null。


## 关键点解析

- 队列

- 队列中用Null(一个特殊元素)来划分每层

- 树的基本操作- 遍历 - 层次遍历（BFS）


## 代码

* 语言支持：JS，C++

JavaScript Code：

```js
/*
 * @lc app=leetcode id=103 lang=javascript
 *
 * [103] Binary Tree Zigzag Level Order Traversal
 *
 * https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/
 *
 * algorithms
 * Medium (40.57%)
 * Total Accepted:    201.2K
 * Total Submissions: 493.7K
 * Testcase Example:  '[3,9,20,null,null,15,7]'
 *
 * 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],
 * 
 * ⁠   3
 * ⁠  / \
 * ⁠ 9  20
 * ⁠   /  \
 * ⁠  15   7
 * 
 * 
 * 
 * return its zigzag level order traversal as:
 * 
 * [
 * ⁠ [3],
 * ⁠ [20,9],
 * ⁠ [15,7]
 * ]
 * 
 * 
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function(root) {
  if (!root) return [];   
  const items = [];
  let isOdd = true;
  let levelNodes = [];
  
  const queue = [root, null];


  while(queue.length > 0) {
      const t = queue.shift();

      if (t) {
          levelNodes.push(t.val)
          if (t.left) {
            queue.push(t.left)
          }
          if (t.right) {
            queue.push(t.right)
          }
      } else {
        if (!isOdd) {
          levelNodes = levelNodes.reverse();
        }
        items.push(levelNodes)
        levelNodes = [];
        isOdd = !isOdd;
        if (queue.length > 0) {
            queue.push(null);
        }
      }
  }

  return items
    
};
```
C++ Code：
```C++
/**
 * 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) {
        auto ret = vector<vector<int>>();
        if (root == nullptr) return ret;
        auto queue = vector<const TreeNode*>{root};
        auto isOdd = true;
        while (!queue.empty()) {
            auto sz = queue.size();
            auto level = vector<int>();
            for (auto i = 0; i < sz; ++i) {
                auto n = queue.front();
                queue.erase(queue.begin());
                if (isOdd) level.push_back(n->val);
                else level.insert(level.begin(), n->val);
                if (n->left != nullptr) queue.push_back(n->left);
                if (n->right != nullptr) queue.push_back(n->right);
            }
            isOdd = !isOdd;
            ret.push_back(level);
        }
        return ret;
    }
};
```
## 拓展

由于二叉树是递归结构，因此，可以采用递归的方式来处理。在递归时需要保留当前的层次信息（从0开始），作为参数传递给下一次递归调用。

### 描述

1. 当前层次为偶数时，将当前节点放到当前层的结果数组尾部
2. 当前层次为奇数时，将当前节点放到当前层的结果数组头部
3. 递归对左子树进行之字形遍历，层数参数为当前层数+1
4. 递归对右子树进行之字形遍历，层数参数为当前层数+1

### C++实现

```C++
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        auto ret = vector<vector<int>>();
        zigzagLevelOrder(root, 0, ret);
        return ret;
    }
private:
    void zigzagLevelOrder(const TreeNode* root, int level, vector<vector<int>>& ret) {
        if (root == nullptr || level < 0) return;
        if (ret.size() <= level) {
            ret.push_back(vector<int>());
        }
        if (level % 2 == 0) ret[level].push_back(root->val);
        else ret[level].insert(ret[level].begin(), root->val);
        zigzagLevelOrder(root->left, level + 1, ret);
        zigzagLevelOrder(root->right, level + 1, ret);
    }
};
```

## 相关题目
- [102.binary-tree-level-order-traversal](./102.binary-tree-level-order-traversal.md)
- [104.maximum-depth-of-binary-tree](./104.maximum-depth-of-binary-tree.md)