C语言 | Leetcode C语言题解之第449题序列化和反序列化二叉搜索树

题目：

题解：

#define MAX_NODE_SIZE 10000

void postOrder(struct TreeNode *root, int *arr, int *pos) {
    if (root == NULL) {
        return;
    }
    postOrder(root->left, arr, pos);
    postOrder(root->right, arr, pos);
    arr[(*pos)++] = root->val;
}

struct TreeNode * construct(int lower, int upper, int *stack, int *top) {
    if (*top == 0 || stack[*top - 1] < lower || stack[*top - 1] > upper) {
        return NULL;
    }
    int val = stack[*top - 1];
    (*top)--;
    struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->val = val;
    root->right = construct(val, upper, stack, top);
    root->left = construct(lower, val, stack, top);
    return root;
}

char* serialize(struct TreeNode* root) {
    char *res = NULL;
    int *arr = (int *)malloc(sizeof(int) * MAX_NODE_SIZE);
    int pos = 0;
    postOrder(root, arr, &pos);
    if (pos == 0) {
        return "";
    }
    res = (char *)malloc(sizeof(char) * pos * 6);
    int len = 0;
    for (int i = 0; i < pos - 1; i++) {
        len += sprintf(res + len, "%d,", arr[i]);
    }
    sprintf(res + len, "%d", arr[pos - 1]);
    free(arr);
    return res;
}

struct TreeNode* deserialize(char* data) {
    int len = strlen(data);
    if (len == 0) {
        return NULL;
    }
    int *stack = (int *)malloc(sizeof(int) * MAX_NODE_SIZE);
    int pos = 0;
    int top = 0;
    while (pos < len) {
        while (pos < len && data[pos] == ',') {
            pos++;
        }
        int val = 0;
        int start = pos;
        while (pos < len && data[pos] != ',') {
            val = val * 10 + data[pos] - '0';
            pos++;
        }
        if (start < pos) {
            stack[top++] = val;
        }
    }
    struct TreeNode *root = construct(INT_MIN, INT_MAX, stack, &top);
    free(stack);
    return root;
}