剑指offer 50.序列化二叉树

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

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

数据范围

树中节点数量 [0,1000]。

样例

你可以序列化如下的二叉树
    8
   / 
  12  2
     / 
    6   4

为："[8, 12, 2, null, null, 6, 4, null, null, null, null]"

class Solution {
public:
    //序列化二叉树，并能反序列，本地是按照前序遍历，即 根  左  右
    //该题也学到了两个技巧一个to_string,一个已知数字字符串的左右端点转为数字
    // Encodes a tree to a single string.
    //二叉树转化为字符串
    string serialize(TreeNode* root) {
        string res; //定义答案
        dfs_s(root,res);//递归处理
        return res;
    }
    void dfs_s(TreeNode*root,string&res) //res为地址传递，所以不用返回string了
    {
        if(!root)  //如果根节点为空
        {
            res+="null "; //在后面加入null和空格
            return ;
        }
        res+=to_string(root->val)+' ';//res加上该节点的val值和一个空格
        dfs_s(root->left,res);//递归处理左右子树
        dfs_s(root->right,res);
    }
    //将上述字符串反序列化为二叉树
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int u=0;
        return dfs_d(data,u);
    }
    TreeNode* dfs_d(string data,int &u)  //u为地址传递
    {   
         if(u==data.size())  return NULL;//如果U到了字符串尾端则退出
        int k=u;
        while(data[k]!=' ') k++; //将k更新到连续数字后面的空格，或者更新到null后面的空格
        if(data[u]=='n') //如果u到了null的n，则说明该节点没有孩子节点，此时应该直接跳过后面的递归左右儿子
        {
            u=k+1; //同时要将u更新成下个结点，即null和空格后面的那个位置
            return NULL;
        }
        int val=0,sign=1;
        if(uleft=dfs_d(data,u);//递归处理该节点的左右子树
        root->right=dfs_d(data,u);
        return root;
    }

};