leetcode 链接：二叉树的锯齿形层序遍历
《程序员面试金典（第 6 版）》中类似题目：[中等] 4.3 特定深度节点链表

题目

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

示例：

给定二叉树 [3,9,20,null,null,15,7],
```
  3
 / \
9  20
  /  \
 15   7
```

返回锯齿形层序遍历如下：

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

解答 & 代码

就是层序遍历，只是偶数行（包括第 0 行）从左往右遍历，奇数行从右往左遍历

/**
* Definition for a binary tree node.
* 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) {}
* };
*/
class Solution {
public:
  vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
      vector<vector<int>> treeList;    // 遍历结果

      if(root == nullptr)        // 别忘了特殊条件处理
          return treeList;

      queue<TreeNode*> nodeQ;
      nodeQ.push(root);

      int depth = 0;            // 深度（层数）
      while(!nodeQ.empty())
      {
          vector<int> levelList;
          int nodeNum = nodeQ.size();
          for(int i = 0; i < nodeNum; ++i)
          {
              TreeNode* node = nodeQ.front();
              nodeQ.pop();

              if(node->left)
                  nodeQ.push(node->left);
              if(node->right)
                  nodeQ.push(node->right);

              if(depth % 2 == 0)    // 偶数层从左往右遍历，因此每次插入数组末端
                  levelList.push_back(node->val);
              else                // 奇数层从右往左遍历，因此每次插入数组头部
                  levelList.insert(levelList.begin(), node->val);
          }
          treeList.push_back(levelList);
          ++depth;
      }
      return treeList;
  }
};

执行结果： ``` 执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户内存消耗：11.9 MB, 在所有 C++ 提交中击败了 52.15% 的用户 ```

CodeTop 企业题库

[中等] 103. 二叉树的锯齿形层序遍历

题目

解答 & 代码