【二叉树】二叉树的层序遍历

二叉树的层序遍历

本文只是节选公众号的中的一篇，我的公众号每日都会更新，欢迎参观 公众号算法每日一更

• 解法一：迭代法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/* 关于本类题的参数：
 res是自己要申请的返回值
 returnSize 要返回行数，因此是整型指针
 returnColumnSizes 要返回（*returnSize）个列数，因此是一维数组的指针
*/

/**
 * 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){
    *returnSize = 0;
    if(root == NULL)    return NULL;
    int** res = (int**)malloc(sizeof(int*) * 2000);
    *returnColumnSizes = (int*)malloc(sizeof(int) * 2000);
    struct TreeNode* data[2001];
    int front = 0, rear = 0;
    struct TreeNode* cur;
    
    data[rear++] = root;
    while(front != rear){
        int colSize = 0;
        int last = rear;
        // 申请本层所需列数
        res[*returnSize] = (int*)malloc(sizeof(int) * (last - front));
        while(front < last){
            // 取出本层内容
            cur = data[front++];
            res[*returnSize][colSize++] = cur -> val;
            // 存入下一层内容
            if(cur -> left != NULL)
                data[rear++] = cur -> left;
            if(cur -> right != NULL)
                data[rear++] = cur -> right;
        }
        // 更新行数列数
        (*returnColumnSizes)[*returnSize] = colSize;
        (*returnSize)++;
    }
    return res;
}

• 解法二：深度优先（DFS）

/**
 * 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().
 */
struct Queue{
    struct TreeNode* node;
    struct Queue* next;
};

// 插入到队尾
void enQueue(struct Queue * queueHead, struct TreeNode* node){
    struct Queue* queueIt = queueHead;
    while(queueIt -> next != NULL){
        queueIt = queueIt -> next;
    }
    struct Queue* queueNew = malloc(sizeof(struct Queue));
    queueNew -> node = node;
    queueNew -> next = NULL;
    queueIt -> next = queueNew;
}

// 从队头删除
struct TreeNode* deQueue(struct Queue* queueHead){
    struct Queue* queueIt = queueHead -> next;
    struct TreeNode* node;
    if(queueIt != NULL){
        queueHead -> next = queueIt -> next;
        node = queueIt -> node;
        free(queueIt);
        return node;
    }
    return NULL;
}

void freeQueue(struct Queue* queueHead){
    // 清理链表
    struct Queue* queueIt = queueHead -> next;
    struct Queue* queuePre = queueHead -> next;
    if(queueIt != NULL){
        queuePre = queueIt;
        queueIt = queueIt -> next;
        free(queuePre);
    }
    free(queueHead);
}

void bfs(int* returnSize, int** returnColumnSizes, int** res, struct Queue* queueHead){
    struct Queue* queueIt = queueHead -> next;
    if(queueIt -> node == NULL)
        return;
    int count = 0;
    res[*returnSize] = (int*)malloc(sizeof(int) * 2000);
    while(1){
        struct TreeNode* node = deQueue(queueHead);
        if(node == NULL)    break;
        // 读队列内容
        res[*returnSize][count++] = node -> val;
        
        // 下一层入队
        if(node -> left != NULL)
            enQueue(queueHead, node -> left);
        if(node -> right != NULL)
            enQueue(queueHead, node -> right);
    }
    enQueue(queueHead, NULL);
    (*returnColumnSizes)[*returnSize] = count;
    *returnSize = *returnSize + 1;
    bfs(returnSize, returnColumnSizes, res, queueHead);
}

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    *returnSize = 0;
    if(root == NULL)    return NULL;
    int** res = (int**)malloc(sizeof(int*) * 2000);
    *returnColumnSizes = (int*)malloc(sizeof(int) * 2000);
    struct Queue *queueHead = malloc(sizeof(struct Queue));
    queueHead -> next = NULL;
    queueHead -> node = NULL;
    enQueue(queueHead, root);
    enQueue(queueHead, NULL);
    
    bfs(returnSize, returnColumnSizes, res, queueHead);
    free(queueHead);
    return res;
}

明天题就来了