(leetcode)二叉树的层次遍历-c语言实现

这段代码，在后面跑测试用例时，出现了stack-overflow，但是原因还不清楚。

问题如下：

二叉树的层次遍历

给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。

例如:
给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果：

[

  [3],

  [9,20],

  [15,7]

]

因为要输出一个二维数组，那么我需要定义一个两重链表，具体定义如下：

/* 链表节点 用于存储输出结果 */

struct listNode {

    int val;

    struct listNode *next;

};

struct list {

    int count;

    struct listNode *head;

    struct listNode *tail;

    struct list *next;

};

struct list_list

{

    int count;

    struct list *head;

    struct list *tail;

};

链表的一些操作如下：

void init_list(struct list *l)

{

    l->count = 0;

    l->head = NULL;

    l->tail = NULL;

    l->next = NULL;

}

void init_list_list(struct list_list *l)

{

    l->count = 0;

    l->head = NULL;

    l->tail = NULL;

}

void add_new_node(struct list *l, struct listNode *node)

{

    if (!l->head)

    {

        l->head = node;

        l->tail = node;

        l->count = 1;

        return;

    }

    l->tail->next = node;

    l->tail = node;

    l->count++;

}

void add_new_list(struct list_list *ll, struct list *l)

{

    if (ll->head == NULL)

    {

        ll->head = l;

        ll->tail = l;

        ll->count = 1;

        return;

    }

    ll->tail->next = l;

    ll->tail = l;

    ll->count++;

}

链表创建如下：

struct list_list * create_list_list()

{

    struct list_list *ll = malloc(sizeof(struct list_list));

    if (ll)

    {

        init_list_list(ll);

    }

    return ll;

}

struct list * create_list()

{

    struct list *l = malloc(sizeof(struct list));

    if (l)

    {

        init_list(l);

    }

    return l;

}

另外需要定义一个队列，用于存放每个树节点

/* 队列节点，用于存储已经遍历过的根节点 */

struct queue_node

{

    void *entry;

    struct queue_node *next;

};

struct queue {

    struct queue_node *front;

    struct queue_node *rear;

};

队列的一些简单操作实现如下：

/* 队列节点，用于存储已经遍历过的根节点 */

struct queue_node

{

    void *entry;

    struct queue_node *next;

};

struct queue {

    struct queue_node *front;

    struct queue_node *rear;

};

void init_queue(struct queue *q)

{

    q->front = NULL;

    q->rear = NULL;

}

void queue_push(struct queue *q, void *np)

{

    struct queue_node *node = malloc(sizeof(struct queue_node));

    node->entry = np;

    node->next = NULL;

    if (q->rear == NULL)

    {

        q->rear = node;

        q->front = node;

    }

    else

    {

        q->rear->next = node;

        q->rear = node;

    }

}

void *queue_pop(struct queue *q)

{

    struct queue_node *np = q->front;

    void *entry = NULL;

    if (np)

    {

        entry = np->entry;

        if (np->next == NULL)

            q->rear = NULL;

        q->front = np->next;

        free(np);

    }

    return entry;

}

struct queue * create_queue()

{

    struct queue *q = malloc(sizeof(struct queue));

    if (q)

    {

        init_queue(q);

    }

    return q;

}

主函数的具体实现思想为，遍历根节点，将其存入队列中，然后在队列中插入一个flag标记，之后进入一个while循环，循环中，每次从队列中取出一个成员，将该成员存入到用于输出的二层链表中，然后判断其左右孩子是否为空，不为空，则其左右孩子入队列。然后再循环，当从队列中取出的是flag标志后，并且队列中还没空，那么就在这个队列中再插入一个flag标志，表示这一层的遍历结束，可以输出这一层的链表。如此循环，直到所有节点都入队列，读到最后一个flag标记，并且队列为空，那么整个遍历流程结束。后面就是把二层链表输出成一个二维数组。

代码如下：

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){

    struct list_list *ll;

    struct list *subList;

    struct listNode *head;

    struct queue *q;

    struct TreeNode *pNode = NULL;

    struct listNode *newnode = NULL;

    int **r;

    int *subr;

    struct list *l;

    int i,j;

    int *size;

    int *resize;

    if (!root || !returnSize || !returnColumnSizes)

        return;

    q = create_queue();

    ll = create_list_list();

    l = create_list();

    add_new_list(ll, l);

    queue_push(q, (void*)root);

    queue_push(q, FINISH_FALG);

    while (q->front != NULL)

    {

        pNode = (struct TreeNode *)queue_pop(q);

        if (pNode == FINISH_FALG)

        {

            if (q->front == NULL)

                break;

            /* 创建新的链表，在总链表中插入新的链表 */

            l = create_list();

            add_new_list(ll, l);

            /* 在当前队列中再插入一个终结标志 */

            queue_push(q, FINISH_FALG);

            continue;

        }

        /* 该节点插入到当前链表中 */

        newnode = create_node(pNode->val);

        add_new_node(l, newnode);

        /* 将当前节点的左右孩子加入队列中 */

        if (pNode->left != NULL)

        {

            queue_push(q, (void*)pNode->left);

        }

        if (pNode->right != NULL)

        {

            queue_push(q, (void*)pNode->right);

        }

    }

    r = (int **)malloc(sizeof(int *) * ll->count);

    resize = (int *)malloc(sizeof(int *) * ll->count);

    subList = ll->head;

    while(subList && i < ll->count)

    {

        subr = (int *)malloc(sizeof(int) * subList->count);

        head = subList->head;

        j = 0;

        while(head && j < subList->count)

        {

            subr[j] = head->val;

            j++;

            head = head->next;

        }

        resize[i] = subList->count;

        r[i] = subr;

        i++;

        subList = subList->next;

    }

    *returnSize = ll->count;

    *returnColumnSizes = resize;

    return r;

}

巴特西

(leetcode)二叉树的层次遍历-c语言实现

最新文章

热门文章