题目描述

请实现两个函数，分别用来序列化和反序列化二叉树。

您需要确保二叉树可以序列化为字符串，并且可以将此字符串反序列化为原始树结构。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void dfs_s(TreeNode* root, string &s)
    {
        if(root == NULL)
        {
            s += "null ";
            return;
        }
        s += to_string(root->val) + ' ';
        dfs_s(root->left, s);
        dfs_s(root->right, s);
    }
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string s;
        dfs_s(root, s);
        //for(auto x : s) cout << x; cout << endl;
        return s;
    }

    TreeNode* dfs_d(string data, int &u)
    {
        if(u == data.size()) return NULL;
        int k = u;
        while(data[k] != ' ') ++k;
        if(data[u] == 'n') {
            u = k + 1;
            return NULL;
        }
        int val = 0, sig = 1; // 判断是否有负数的情况
        if(data[u] == '-')
        {
            u++; sig = -1;
        }
        for(int i = u; i < k; ++i) val = 10 * val + data[i] - '0';
        val = sig * val; // 如果有负数，需要乘以-1， 没有乘以1
        TreeNode* node = new TreeNode(val);
        u = k + 1;
        node->left = dfs_d(data, u);
        node->right = dfs_d(data, u);
        return node;
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int u = 0;
        return dfs_d(data, u);
    }
};