2026/05/02

[LeetCode] 297 Serialize and Deserialize Binary Tree

因為會用自產自銷的方式來測試serialize

所以要怎麼表示nullptr的節點可以自己決定

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
private:
  static constexpr char NULLVAL = 'X';
  void serializeImpl(TreeNode *root, ostringstream &os) {
    if (root) {
      os << root->val << ' ';
      serializeImpl(root->left, os);
      serializeImpl(root->right, os);
    }
    else 
      os << NULLVAL << ' ';
  }

  TreeNode* deserializeImpl(istringstream &is) {
    string str;
    is >> str;
    if (str.size() == 1 && str[0] == NULLVAL) 
      return nullptr;
    TreeNode *root = new TreeNode(std::stoi(str));
    root->left = deserializeImpl(is);
    root->right = deserializeImpl(is);
    return root;
  }

public:

  // Encodes a tree to a single string.
  string serialize(TreeNode* root) {
    ostringstream os;
    serializeImpl(root, os);
    return os.str();
  }

  // Decodes your encoded data to tree.
  TreeNode* deserialize(string data) {
    istringstream is(data);
    return deserializeImpl(is);
  }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));
Labels: