为什么我无法从下面的代码中获得二叉树级别的顺序遍历？

Question

我正在尝试对二叉搜索树进行一次级别顺序遍历，并在多维数组中返回最终结果。例如，如果根节点是2，而级别1的节点是1,4，那么它应该从代码返回[[2]，[1,4]]作为returnColumnSizes。我是数据结构方面的新手，也没有使用malloc函数的命令。任何帮助都将不胜感激。谢谢：）

int height(struct TreeNode *h){
    if (h == NULL) return 0;
    int l = height(h->left);
    int r = height(h->right);
    if (l > r)
        return l+1;
    else
        return r+1;
}

int *ordercalc(struct TreeNode *root, int level){
    if (root == NULL) return NULL;
    int i = 0, arr[100];
    if (level == 1)
        arr[i++] = root->val;
    else if(level > 1){
        ordercalc(root->left, level-1);  //decrease the level one per call to print data when it
        ordercalc(root->right, level-1);  // reaches proper level
    }
    return arr;
}

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    if (*returnSize == 0) return NULL;
    **returnColumnSizes = (int **)malloc(*returnSize * sizeof(int *));
    for (int i=0;i<height(root)+1;i++){
        returnColumnSizes[i] = (int *)malloc(sizeof(int) * 10);
        returnColumnSizes[i] = ordercalc(root, i);
    }
    return returnColumnSizes;
}

Answer 1

高度看起来不错。

levelOrder看起来不错，不过i

ordercalc需要重新考虑。函数在其堆栈框架上分配了arr[100]；

if (level == 1)
    arr[i++] = root->val;

和

return arr;

我可以看到你试图根据高度来填充水平，这是正确的想法。然而：

1. 返回堆栈分配的数组是未定义的行为。当调用返回时，无法访问其帧上的所有数据。如果要执行此操作，需要在堆上malloc，并返回一个指针

与此函数返回结果不同，传入指向预分配结果结构的指针似乎是最简单的。

简化重新分配和大小管理的一种方法是使用多个过程来处理问题。以下是游戏计划：

1. 获取树的高度

这是代码：

int height(struct TreeNode *root) {
    if (root) {
        int left = height(root->left);
        int right = height(root->right);
        return 1 + (left > right ? left : right);
    }

    return 0;
}

void set_col_lens(struct TreeNode *root, int *res_col_lens, int depth) {
    if (root) {
        res_col_lens[depth]++;
        set_col_lens(root->left, res_col_lens, depth + 1);
        set_col_lens(root->right, res_col_lens, depth + 1);
    }
}

void fill_levels(struct TreeNode *root, int **res, int *last_items, int level) {
    if (root) {
        int last_item = last_items[level]++;
        res[level][last_item] = root->val;
        fill_levels(root->left, res, last_items, level + 1);
        fill_levels(root->right, res, last_items, level + 1);
    }
}

int **level_order(struct TreeNode *root, int *res_len, int **res_col_lens) {
    if (!root) {
        *res_len = 0;
        return NULL;
    }

    *res_len = height(root);
    int **res = malloc(sizeof(*res) * (*res_len));
    *res_col_lens = calloc(*res_len, sizeof(**res_col_lens));
    int *last_items = calloc(*res_len, sizeof(*last_items));
    set_col_lens(root, *res_col_lens, 0);

    for (int i = 0; i < *res_len; i++) {
        res[i] = malloc(sizeof((*res)[i]) * (*res_col_lens)[i]);
    }

    fill_levels(root, res, last_items, 0);
    free(last_items);
    return res;
}

这样做的一个好处是，问题被分成简单、不同的步骤。

我认为更自然的另一种方法是使用队列并在一个堆栈帧中执行广度优先遍历。然后，问题变成了用C编写队列抽象，这并不难，但确实需要一点大惊小怪。