[Day 12] LeetCode 75 - 102. Binary Tree Level Order Traversal

14th鐵人賽 c leetcode

eric1864

2022-09-24 20:12:11

1072 瀏覽

分享至

LeetCode 75 Level 1 - Day 6 Tree

102. Binary Tree Level Order Traversal

題目連結
難易度：Medium

題目敘述

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

預設函數

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){

}

題目限制

The number of nodes in the tree is in the range [0, 2000].
-1000 <= Node.val <= 1000

解題過程及程式碼

本題是 Tree的第二題，給一個二元樹，需要依階層回傳每個節點的數值，例如下圖是題目所給Example 1，需回傳一個二維的陣列Output: [[3],[9,20],[15,7]]，第0層節點有3，第1層節點有9和20，第3層節點有15和7。

image alt

由於本題需要回傳一個二維陣列，需先了解C語言中二維陣列要如何傳遞，例如以下的程式碼，首先我們需要一個指標 dynArr和整數 returnSize，像陣列一樣用來記錄二維陣列裡每一列有幾個元素，再來需要二維陣列資料本體的 dynArr2D，它是指標的指標，記錄著二維陣列中每一列的指標，有了這三個部件我們就可以在C語言中完整描述一個二維陣列。

二維動態記憶體配置程式碼

#define ROW 2000
#define COL 150
#define HEIGHT 800

int *dynArr;
int **dynArr2D;

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    dynArr = (int *)calloc(HEIGHT, sizeof(int));        /* 動態記憶體配置 */

    dynArr2D = (int **)malloc(sizeof(int *) * ROW);         /* 動態記憶體配置 */
    for (int i=0; i<ROW; i++) {
        dynArr2D[i] = (int *)malloc(sizeof(int) * COL);     /* 動態記憶體配置 */
    }

    *returnColumnSizes = dynArr;  // 要回應一個陣列表示每一層有多少節點
    *returnSize = 1;  // 要指出*returnColumnSizes這個陣列有多長
    return NULL;
}

本題想法是用 while迴圈，從 root走遍所有的節點，並把節點資料和它所在的層數一起丟到先進先出的 queue裡，再從queue裡一個一個拿出來放進二維陣列裡，為此我們需要實現一個簡單的queue，例如以下程式碼， addq函數用來加入至 queue裡， deleteq函數用來取出一個元素， isEmpty函數用來確認目前 queue裡是不是空的。

queue程式碼

#define MAX_QUEUE_SIZE 100

typedef struct {
    int key;
} element;

void addq(element);
element deleteq(void);
int isEmpty(void);

element queue[MAX_QUEUE_SIZE];
int rear = 0;
int front = 0;

int main() {
    element item1, item2;
    item1.key = 7;
    item2.key = 9;
    addq(item1);
    addq(item2);
    printf ("deleteq: %d\n", deleteq().key);
    printf ("deleteq: %d\n", deleteq().key);
    return 0;
}

void addq(element item) {
    rear = (rear + 1) % MAX_QUEUE_SIZE;
    if (front == rear) {
        // queueFull();
    }
    queue[rear] = item;
}

element deleteq(void) {
    element item;
    if (front == rear) {
        // return queueEmpty();
    }
    front = (front + 1) % MAX_QUEUE_SIZE;
    return queue[front];
}

int isEmpty(void) {
    if (front == rear) {
        return 1;
    } else {
        return 0;
    }
}

最後程式碼上傳如下

#define ROW 800
#define COL 150
#define HEIGHT 800

#define MAX_QUEUE_SIZE 150

typedef struct {
    struct TreeNode* key;
    int level;
} element;

element *deleteq(void);
element queue[MAX_QUEUE_SIZE];
int front;
int rear;

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    int *dynArr = (int *)calloc(HEIGHT, sizeof(int));

    int **dynArr2D = (int **)malloc(sizeof(int *) * ROW);
    for (int i=0; i<ROW; i++) {
        dynArr2D[i] = (int *)malloc(sizeof(int) * COL);
    }

    *returnSize = run_preorder3(root, dynArr, dynArr2D);
    *returnColumnSizes = dynArr;
    return dynArr2D;
}

int run_preorder3(struct TreeNode *ptr, int *array, int **array2D) {
    int node_level = 0;
    element *e;

    if (ptr == NULL) return 0;

    addq(ptr, 0);
    while (!isEmpty()) {
        e = deleteq();

        if (node_level <= e->level) {
            node_level = e->level;
        }

        ptr = e->key;
        if (ptr != NULL) {
            array2D[e->level][++array[e->level] - 1]= ptr->val;

            if ((ptr->left) != NULL) {
                addq(ptr->left, e->level + 1);
            }

            if ((ptr->right) != NULL) {
                addq(ptr->right, e->level + 1);
            }
        } else {
            break;
        }
    }
    return node_level + 1;
}

void addq(struct TreeNode* ptr, int lv) {
    rear = (rear + 1) % MAX_QUEUE_SIZE;
    queue[rear].key = ptr;
    queue[rear].level = lv;
}

element *deleteq(void) {
    front = (front + 1) % MAX_QUEUE_SIZE;
    return (queue + front);
}

int isEmpty(void) {
    return (front == rear);
}

下方有解法的參考資料，今天到此謝謝大家!