LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 层次序遍历，用 # 表示空节点

  1
 / \
2   3
   / \
  4   5

     1
   /   \
  2     3
 / \   / \
#   # 4   5
     / \ / \
    #  # #  #
序列化为：1 2 3 # # 4 5 # # # #

    1
   / \
  2   3
     / \
    4   5
   /
  6

     1
   /   \
  2     3
 / \   / \
#   # 4   5
     / \ / \
    6  # #  #
   / \
  #   #
序列化为：1 2 3 # # 4 5 6 # # # # # 

• 解法如下

class Codec {
 public:
  // Encodes a tree to a single string.
  string serialize(TreeNode* root) {
    if (!root) {
      return "";
    }
    queue<TreeNode*> q;
    q.emplace(root);
    stringstream ss;
    while (!empty(q)) {
      TreeNode* t = q.front();
      q.pop();
      if (t) {
        ss << t->val << " ";
        q.emplace(t->left);
        q.emplace(t->right);
      } else {
        ss << "# ";
      }
    }
    return ss.str();
  }

  // Decodes your encoded data to tree.
  TreeNode* deserialize(string data) {
    if (empty(data)) {
      return nullptr;
    }
    stringstream ss{data};
    string s;
    ss >> s;
    TreeNode* root = new TreeNode(stoi(s));
    queue<TreeNode*> q;
    q.emplace(root);
    while (!empty(q)) {
      TreeNode* t = q.front();
      q.pop();
      ss >> s;
      if (s == "#") {
        t->left = nullptr;
      } else {
        t->left = new TreeNode(stoi(s));
        q.emplace(t->left);
      }
      ss >> s;
      if (s == "#") {
        t->right = nullptr;
      } else {
        t->right = new TreeNode(stoi(s));
        q.emplace(t->right);
      }
    }
    return root;
  }
};