다음 코드에서 이진 트리 수준 순서 순회를 얻을 수없는 이유는 무엇입니까?

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로 큐 추상화를 작성하게되는데, 이는 어렵지 않지만 약간의 소란이 필요합니다.