题目描述

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

题目解读

• 剑指Offer 194
• 参考书上写的，递归思想写的，在牛客网上不知为啥没跑通，但在本地跑通了，很好，时间原因不在牛客网调试了

代码

#include<iostream>
using namespace std;

typedef struct node{
    char val;            //节点信息
    struct node *left;   //左孩子
    struct node *right;  //右孩子
}TreeNode;

// 反序列化二叉树
TreeNode* DeserializeCore(char str[], int *length){
    if(str[(*length)] == '$'){
        (*length)++;
        return NULL;
    }
    else{
        TreeNode* temp = new TreeNode();
        temp->val = str[(*length)];
        temp->left = temp->right = NULL;
        (*length)++;
        temp->left  = DeserializeCore(str, length);
        temp->right = DeserializeCore(str, length); 
        return temp;
    }
}

//创建一颗二叉树
TreeNode* create(){
    char tt[20] = {'1', '2', '4', '$', '$', '$', '3', '5', '$', '$', '6', '$', '$'};
    int length = 0;
    TreeNode* root;

    root = DeserializeCore(tt, &length);
    return root;
}

void SerializeCore(TreeNode *root, char result[], int *length){
    if(root == NULL){
        result[(*length)] = '$';
        (*length)++;
    }
    else{
        result[(*length)] = root->val;;
        (*length)++;
        SerializeCore(root->left, result, length);
        SerializeCore(root->right, result, length);
    }
}

// 序列化二叉树
char* Serialize(TreeNode *root) {    
        int length = 0;
        static char result[100];
       
        SerializeCore(root, result, &length);
        result[length] = '\0';
        return result;
}

// 前序遍历
void qianxu(TreeNode* root){
    if(root){
        cout<<root->val<<" ";
        qianxu(root->left);
        qianxu(root->right);
    }
}

int main(){
    TreeNode* root;
    root = create();
    qianxu(root);
    cout<<endl;
    
    char* ss = Serialize(root);
    cout<<ss;
    return 0;
}

总结展望