題目描述

• 請實(shí)現(xiàn)兩個(gè)函數(shù)，分別用來序列化和反序列化二叉樹

題目解讀

• 劍指Offer 194
• 參考書上寫的，遞歸思想寫的，在?？途W(wǎng)上不知為啥沒跑通，但在本地跑通了，很好，時(shí)間原因不在牛客網(wǎng)調(diào)試了

代碼

#include<iostream>
using namespace std;

typedef struct node{
    char val;            //節(jié)點(diǎn)信息
    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;
    }
}

//創(chuàng)建一顆二叉樹
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;
}

總結(jié)展望