题解 | #序列化二叉树#

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
#include <cstddef>
#include <cstring>
#include <string>
#include <vector>
class Solution {
public:

    void preOrder(TreeNode* root, string& res){
        // 将以root为根节点的子树以先序遍历的顺序添加到res中。
        if(root == NULL){
            res += "#";
            return;
        }
        //先将根节点添加到res中。
        int val = root->val;
        res+=to_string(val);
        res+="!";

        //将左子树存储到res中。
        preOrder(root->left, res);
        preOrder(root->right, res);
    }
    char* Serialize(TreeNode *root) {    
        // 
        string res;
        preOrder(root, res);
        //将string转化为char*
        char* treeSerial = new char[res.size()+1];
        strcpy(treeSerial, res.c_str());
        treeSerial[res.size()] = '\0';
        return treeSerial;
    }

    TreeNode* preDe(char* s, int& p){
        // 返回字符串s[p..]所对应的第一棵二叉树的先序遍历所对应的二叉树的根节点，并创建这一棵二叉树
        if(s[p] == '#'){
            p++;
            return nullptr;
        }
        
        // 建立根节点
        //读取根节点的符号
        bool is_positive = true;
        if(s[p] == '-'){
            is_positive = false;
            p++;
        }
        int val = 0;
        while(s[p]!='!'){
            val = val * 10 + s[p] - '0';
            p++;
        }
        
        //构建根节点
        TreeNode* root = new TreeNode(val);
        p++;
        root->left = preDe(s,p);
        root->right = preDe(s,p);
        return root;
    

    }
       
    
    TreeNode* Deserialize(char *str) {
      int p = 0;
      auto res = preDe(str, p);
      return res;
    }
};

通过本题，我对掌握递归有了新的技巧。掌握递归的关键在于用一个包含函数输入和函数返回类型的文字语言将函数的功能清晰表达。