题解 | #序列化二叉树#

一开始想复杂了，其实怎么拆分就怎么还原，也不需要按照每一层每一层这样记录下满二叉树。

用的层次遍历思想，但是不要分层去拆。

class Solution {
public:
    //  !作为每组数字的结尾，空节点用#表示
    char* Serialize(TreeNode *root) {    
      if (!root) {
        return nullptr;
      }
      std::string str;
      std::queue tree;
      tree.push(root);
      str += std::to_string(root->val) + '!';
      while (!tree.empty()) {
        TreeNode *cur = tree.front();
        tree.pop();
        if (cur->left) {
          tree.push(cur->left);
          str += std::to_string(cur->left->val) + '!';
        } else {
          str += '#';
        }
        if (cur->right) {
          tree.push(cur->right);
          str += std::to_string(cur->right->val) + '!';
        } else {
          str += '#';
        }
      }
      char *res = new char[str.size() + 1];
      std::strcpy(res, str.c_str());
      return res;
    }
    TreeNode* Deserialize(char *str) {
      if (!str) {
        return nullptr;
      }
      std::string list = str;
      std::vector s;
      std::queue tree;
      int i = 0;
      while (i < list.size()) {
        if (list[i] == '#') {
          s.push_back(std::string("#"));
          ++i;
          continue;
        }
        int j = i;
        while (list[j] != '!') {
          ++j;
        }
        s.push_back(list.substr(i, j - i));
        i = j + 1;
      }
      i = 1;
      TreeNode *root = new TreeNode(std::stoi(s[0]));
      tree.push(root);
      while (i < s.size()) {
        TreeNode *cur = tree.front();
        tree.pop();
        cur->left = cur->right = nullptr;
        if (s[i] != "#") {
          cur->left = new TreeNode(std::stoi(s[i]));
          tree.push(cur->left);
        }
        if (s[i+1] != "#") {
          cur->right = new TreeNode(std::stoi(s[i+1]));
          tree.push(cur->right);
        }
        i += 2;
      }
      return root;
    }
};