二叉树序列化

    1. class Codec {
    2. public:
    3.     string serialize(TreeNode* root) {
    4.         if (!root) {
    5.             return "X";
    6.         }
    7.         auto left = "(" + serialize(root->left) + ")";
    8.         auto right = "(" + serialize(root->right) + ")";
    9.         return left + to_string(root->val) + right;
    10.     }
    12.     inline TreeNode* parseSubtree(const string &data, int &ptr) {
    13.         ++ptr; // 跳过左括号
    14.         auto subtree = parse(data, ptr);
    15.         ++ptr; // 跳过右括号
    16.         return subtree;
    17.     }
    19.     inline int parseInt(const string &data, int &ptr) {
    20.         int x = 0, sgn = 1;
    21.         if (!isdigit(data[ptr])) {
    22.             sgn = -1;
    23.             ++ptr;
    24.         }
    25.         while (isdigit(data[ptr])) {
    26.             x = x * 10 + data[ptr++] - '0';
    27.         }
    28.         return x * sgn;
    29.     }
    31.     TreeNode* parse(const string &data, int &ptr) {
    32.         if (data[ptr] == 'X') {
    33.             ++ptr;
    34.             return nullptr;
    35.         }
    36.         auto cur = new TreeNode(0);
    37.         cur->left = parseSubtree(data, ptr);
    38.         cur->val = parseInt(data, ptr);
    39.         cur->right = parseSubtree(data, ptr);
    40.         return cur;
    41.     }
    43.     TreeNode* deserialize(string data) {
    44.         int ptr = 0;
    45.         return parse(data, ptr);
    46.     }
    47. };