103. 二叉樹的鋸齒形層次遍歷

• 給定一個(gè)二叉樹，返回其節(jié)點(diǎn)值的鋸齒形層次遍歷。（即先從左往右，再從右往左進(jìn)行下一層遍歷，以此類推，層與層之間交替進(jìn)行）。

示例

  給定二叉樹 [3,9,20,null,null,15,7],
      3
    / \
    9  20
      /  \
    15   7
  返回鋸齒形層次遍歷如下：
    [
      [3],
      [20,9],
      [15,7]
    ]

思路

1. 利用隊(duì)列實(shí)現(xiàn)層次遍歷，bool變量標(biāo)識(shí)是否需要反轉(zhuǎn)。
2. 注意不需要使用兩個(gè)隊(duì)列來標(biāo)記‘層’的信息，每次遍歷時(shí)直接取出該層元素個(gè)數(shù)即可。

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;
  }
};