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

Question

我正在尝试遍历二进制搜索树，并以多维数组形式返回最终结果。例如。如果root node为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

height看起来不错。

levelOrder看起来还不错，尽管i<height(root)+1;即使不改变，也在循环中一次又一次地计算root的高度。另外，对于大树，malloc(sizeof(int) * 10);似乎没有足够的动态（我们稍后会再讨论）。

ordercalc需要重新考虑。该函数在其堆栈帧上分配了arr[100];，然后

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

和

return arr;

我可以看到您正在尝试根据高度填充水平，这是正确的想法。但是：

1. 返回堆栈分配的数组是未定义的行为。呼叫返回时，无法访问其框架上的所有数据。如果要执行此操作，则需要在堆上malloc并返回一个指针。
2. [arr[i++] = root->val;将根放在arr[0]，但此数组未发生任何其他事情，因此目的不明确。
3. 对数组大小进行硬编码100似乎是一个错误。假设您打算将其填充到根以外，肯定有一些树的大小足以溢出此缓冲区。当您确实切换到malloc时，您可能需要计划将其设置为realloc。

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

简化重新分配和规模管理的一种方法是通过多次通过来解决该问题。这是游戏计划：

1. 获取树的高度。
2. 分配结果和列大小数组以匹配树的高度。
3. 执行第二次遍历并为每个级别设置结果列的长度。
4. 分配每个级别以匹配在步骤3中确定的大小。
5. 执行最后一遍以填充预分配的结果级别。

这里是代码：

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编写队列抽象，这并不困难，但确实需要大惊小怪。