TOP101题解 | BM39#序列化二叉树#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * @author Senky
 * @date 2023.08.04
 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1
 * @brief 层序化
 * @param root TreeNode类 
 * @return char字符型一维数组
 */

// Serialize the binary tree to a string
void serializeHelper(struct TreeNode* root, char* result, int* idx) {
    if (root == NULL) 
    {
        strcat(result, "#,");
        return;
    }
    
    char temp[20];
    sprintf(temp, "%d,", root->val);
    strcat(result, temp);
    
    serializeHelper(root->left, result, idx);
    serializeHelper(root->right, result, idx);
}

char* Serialize(struct TreeNode* root) 
{
    if (root == NULL) 
    {
        return "";
    }
    
    char* result = (char*)malloc(1000 * sizeof(char));
    strcpy(result, "");
    int idx = 0;
    
    serializeHelper(root, result, &idx);
    
    result[strlen(result) - 1] = '\0'; // Remove the last comma
    return result;
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * @author Senky
 * @date 2023.08.04
 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1
 * @brief 层序化转变成二叉树
 * @param str char字符型一维数组 
 * @return TreeNode类
 */

// Deserialize the string to a binary tree
struct TreeNode* deserializeHelper(char* tokens[], int* idx) {
    if (strcmp(tokens[*idx], "#") == 0) {
        (*idx)++;
        return NULL;
    }
    
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = atoi(tokens[*idx]);
    (*idx)++;
    
    root->left = deserializeHelper(tokens, idx);
    root->right = deserializeHelper(tokens, idx);
    
    return root;
}

struct TreeNode* Deserialize(char* str) {
    if (strcmp(str, "") == 0) {
        return NULL;
    }
    
    char* tokens[1000];
    int count = 0;
    char* token = strtok(str, ",");
    while (token != NULL) {
        tokens[count++] = token;
        token = strtok(NULL, ",");
    }
    
    int idx = 0;
    return deserializeHelper(tokens, &idx);
}