二叉树的序列化与反序列化

二叉树的序列化与反序列化

297.二叉树的序列化与反序列化

//先序遍历求解
class Codec {
public:
    //将二叉树序列化为字符串
    string serialize(TreeNode* root) {
        string res;
        helper(root, res);
        return res;
    }
    //辅助函数，将二叉树存入string中
    void helper(TreeNode* root, string& s){
        if(root==NULL){
            s += "#,";
        }else{
            s += to_string(root->val) + ",";
            helper(root->left, s);
            helper(root->right, s);
        }
    }

    //将字符串反序列化为二叉树
    TreeNode* deserialize(string data) {
        //将字符串转化成链表
        list<string> lst;
        //借助一个字符串来控制","
        string str; 
        for(auto& ch : data){
            if(ch==','){
                lst.push_back(str);
                str.clear();
            }else{
                str.push_back(ch);
            }
        }
        if(!str.empty()){
            lst.push_back(str);
            str.clear();
        }
        return build(lst);
    }
    //辅助函数，通过链表构造二叉树
    TreeNode* build(list<string>& data){
        if(data.front()=="#"){
            data.erase(data.begin());
            return NULL;
        }

        TreeNode* root = new TreeNode(stoi(data.front()));
        data.erase(data.begin());
        root->left=build(data);
        root->right=build(data);
        return root;
    }
};

//先序遍历求解
type Codec struct {
}

func Constructor() Codec {
    return Codec{}
}

//将二叉树序列化为字符串
func (this *Codec) serialize(root *TreeNode) string {
    var res string
    this.helper(root, &res)
    return res
}

//辅助函数，将二叉树存入string中
func (this *Codec) helper(root *TreeNode, s *string) {
    if root == nil {
        *s += "#,"
    } else {
        *s += strconv.Itoa(root.Val) + ","
        this.helper(root.Left, s)
        this.helper(root.Right, s)
    }
}

//将字符串反序列化为二叉树
func (this *Codec) deserialize(data string) *TreeNode {
    //将字符串转化成切片
    lst := []string{}
    //借助一个字符串来控制","
    str := ""
    for _, ch := range data {
        if ch == ',' {
            lst = append(lst, str)
            str = ""
        } else {
            str += string(ch)
        }
    }
    if str != "" {
        lst = append(lst, str)
        str = ""
    }
    return this.build(&lst)
}

//辅助函数，通过切片构造二叉树
func (this *Codec) build(data *[]string) *TreeNode {
    if (*data)[0] == "#" {
        *data = (*data)[1:]
        return nil
    }

    val, _ := strconv.Atoi((*data)[0])
    root := &TreeNode{Val: val}
    *data = (*data)[1:]
    root.Left = this.build(data)
    root.Right = this.build(data)
    return root
}