欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode 116. 填充每个节点的下一个右侧节点指针 C语言层序遍历实现

程序员文章站 2022-05-20 16:11:16
...

leetcode 116. 填充每个节点的下一个右侧节点指针 C语言层序遍历实现

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *left;
 *     struct Node *right;
 *     struct Node *next;
 * };
 */

struct Node* connect(struct Node* root) {
    if(root == NULL){ //检查根节点是否为空
        return root;
    }
	struct Node * queue[10000];//设计一个简单的队列
    int head=0,rear = 0;
    int level = 0;//用于记录层数,这道题不需要
    root->next = NULL; 
    queue[rear++] = root;
    level = 1;//根节点入队第一层
    
    while(head!=rear){//这里进去的每一个队列只有自己第level层的节点
        int len = rear-head;//队列的长度表示第level层的节点个数
        for(int i =0;i<len;i++){
            struct Node * tmp = queue[head++];
            //一层的节点全部连接起来
            if(i == len-1){
                tmp->next = NULL;
            }else{
                tmp->next = queue[head];
            }
            //左右儿子入队
            if(tmp->left!=NULL){
                queue[rear++] = tmp->left;
            }
            if(tmp->right!=NULL){
                queue[rear++] = tmp->right;
            }
      
        }
        level ++;//for循环结束之后层数加1
    }
    return root;
}