LeetCodeDay45 —— 二叉树的锯齿形层次遍历★☆

103. 二叉树的锯齿形层次遍历

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

示例

  给定二叉树 [3,9,20,null,null,15,7],
      3
    / \
    9  20
      /  \
    15   7
  返回锯齿形层次遍历如下：
    [
      [3],
      [20,9],
      [15,7]
    ]

思路

1. 利用队列实现层次遍历，bool变量标识是否需要反转。
2. 注意不需要使用两个队列来标记‘层’的信息，每次遍历时直接取出该层元素个数即可。

class Solution {
 public:
  vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    if (!root) return {};
    bool needSwitch = false;
    vector<vector<int>> ret;
    queue<TreeNode*> mQue;
    mQue.push(root);
    while (!mQue.empty()) {
      int size = mQue.size();
      vector<int> level;
      while (size--) {
        TreeNode* node = mQue.front();
        mQue.pop();
        level.push_back(node->val);
        if (node->left) mQue.push(node->left);
        if (node->right) mQue.push(node->right);
      }
      if (needSwitch) {
        ret.push_back(vector<int>(level.rbegin(), level.rend()));
      } else {
        ret.push_back(level);
      }
      needSwitch = !needSwitch;
    }
    return ret;
  }
};