leetcode 103 두 갈래 나무의 톱날 모양 차원 반복 C 언어 구현

10366 단어 LeetCode

제목


leetcode103은 두 갈래 나무를 지정하고 노드 값의 톱날 모양 차원을 되돌려줍니다.(즉, 먼저 왼쪽에서 오른쪽으로, 다시 오른쪽에서 왼쪽으로 다음 층을 훑어보며, 이와 같이 층과 층 사이를 교체하여 진행한다.)
예를 들어 주어진 두 갈래 나무[3,9,20,null,null,15,7], 3/9 20/15 7은 톱날 모양의 차원을 다음과 같이 반복한다. [3],[20,9],[15,7]]

코드

int** zigzagLevelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    *returnSize = 0;
    if (root == NULL) return 0;
    #define MAX 1000000
    int **arr = (int **)malloc(sizeof(int *) * MAX);
    (*returnColumnSizes) = (int *)malloc(sizeof(int) * MAX);
    struct TreeNode *q[MAX], *p;
    int front = 0, rear = -1, last = 0;
    q[++rear] = root;
    int num[MAX], k = 0;
    while (front <= rear) {
        p = q[front++];
        num[k++] = p->val;
        if (p->left) q[++rear] = p->left;
        if (p->right) q[++rear] = p->right;
        if (last == front - 1) {
            int j = 0;
            arr[*returnSize] = (int *)malloc(sizeof(int) * k);
            if ((*returnSize) % 2 == 0) {
                for (int i = 0; i < k; i++) 
                    arr[*returnSize][j++] = num[i];
            } else {
                for (int i = k - 1; i >= 0; i--) 
                    arr[*returnSize][j++] = num[i];
            }
            (*returnColumnSizes)[*returnSize] = k;
            (*returnSize)++;
            k = 0;
            last = rear;
        }
    }
    return arr;
}

좋은 웹페이지 즐겨찾기