(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语言实现

相关文章