题解 | #序列化二叉树#

序列化：按照前序遍历的顺序将二叉树序列化为字符串，空节点序列化为 #，非空节点将数字加到字符串中，每个节点之间用 , 分隔(在反序列化中需要得到每个节点的值)。序列化结束将字符串最后的 , 去掉。

反序列化：根据前序序列以及其中包含的空节点就可以还原一棵二叉树。根节点就是前序序列的第一个节点，从字符串中拿到当前节点的值，构建当前节点，递归构建左子树和右子树。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    string s;
    
    void s_dfs(TreeNode* root) {
        if (!root) {
            s += "#,";
            return;
        }
        s += to_string(root->val) + ',';
        s_dfs(root->left);
        s_dfs(root->right);
    }
    
    char* Serialize(TreeNode *root) {    
        if (!root) return nullptr;
        s_dfs(root);
        s = s.substr(0, s.length() - 1);
        char* res = new char[s.length()];
        return res;
    }
    
    TreeNode* d_dfs(string& s, int& k) {
        if (s[k] == '#') {
            k ++ ; // 跳过 #
            k ++ ; // 跳过 ,
            return NULL;
        }
        int val = 0;
        while (s[k] != ',') {
            val = val * 10 + s[k] - '0';
            k ++ ;
        }
        // 跳过 ,
        k ++ ;
        auto root = new TreeNode(val);
        root->left = d_dfs(s, k);
        root->right = d_dfs(s, k);
        return root;
    }
    
    TreeNode* Deserialize(char *str) {
        if (s.empty()) return nullptr;
        int k = 0;
        return d_dfs(s, k);
    }
};