102. 二叉树的层序遍历

102. 二叉树的层序遍历 - 力扣（LeetCode）

class Solution {
public:
  vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> Result;
    if (!root)
      return Result;

    queue<TreeNode *> Q;
    int NodesInCurrLevel = 1;
    int NodesInNextLevel = 0;
    vector<int> *Level = new vector<int>();

    Q.push(root);
    while (!Q.empty()) {
      // Pop front element
      --NodesInCurrLevel;

      TreeNode *TN = Q.front();
      Q.pop();
      if (TN->left) {
        Q.push(TN->left);
        ++NodesInNextLevel;
      }
      if (TN->right) {
        Q.push(TN->right);
        ++NodesInNextLevel;
      }
      Level->push_back(TN->val);

      if (NodesInCurrLevel == 0) {
        Result.push_back(*Level);
        NodesInCurrLevel = NodesInNextLevel;
        NodesInNextLevel = 0;
        Level = new vector<int>();
      }
    }

    return Result;
  }
};

我的代码其实有点好玩，我相当于是手动把这个循环给展开了。但事实上我的写法并不好，因为牵涉到指针，效率低，并且也没有利用到层序遍历的特殊性质，这个特别特别有意思：

queue<TreeNode *> q;
q.push(root);
while (!q.empty()) {
  int currentLevelSize = q.size();
  ret.push_back({});
  for (int i = 0; i < currentLevelSize; ++i) {
    TreeNode *node = q.front();
    q.pop();

    ret.back().push_back(node->val);
    if (node->left)
	  q.push(node->left);
    if (node->right)
	  q.push(node->right);
  }
}

这两层嵌套的循环事实上复杂度仍然是 \(\mathrm O(n)\) 的，并且它保证了每次外层循环都对应整一层。

二刷

class Solution {
public:
  vector<vector<int>> levelOrder(TreeNode* root) {
    std::queue<TreeNode *> Q;
    std::vector<vector<int>> Result;

    if (!root)
      return {};

    Q.push(root);
    while (!Q.empty()) {
      int LayerSize = Q.size();
      Result.push_back({});
      for (int i = 0; i < LayerSize; ++i) {
        TreeNode *This = Q.front();
        Result.back().push_back(This->val);
        Q.pop();
        if (This->left)
          Q.push(This->left);
        if (This->right)
          Q.push(This->right);
      }
    }
    return Result;
  }
};

没什么好说的。

三刷

class Solution {
public:
  vector<vector<int>> levelOrder(TreeNode* root) {
    if (!root)
      return {};

    vector<vector<int>> Result;
    queue<TreeNode *> Q;

    Q.push(root);
    while (!Q.empty()) {
      int LayerSize = Q.size();
      Result.emplace_back();
      for (int i = 0; i < LayerSize; ++i) {
        TreeNode *Cur = Q.front();
        Q.pop();
        Result.back().emplace_back(Cur->val);
        if (Cur->left)
          Q.push(Cur->left);
        if (Cur->right)
          Q.push(Cur->right);
      }
    }
    return Result;
  }
};

其实我一开始还想偷懒省掉if (Cur->left)这种判定，但是后来发现会导致空层，还是算了吧，这应该是最省心的写法了。