Leetcode之填充每个节点的下一个右侧节点指针 II

文章目录

• 前言
• 
  

  一、BFS解决

• 
  

  二、优化

• 总结

前言

题目链接

一、BFS解决

根据题目要求，把二叉树中的每一行都串联起来，这就不难想到用层序遍历来解决问题，层序遍历动图演示如下(第一次做动图，做了半天o(╥﹏╥)o）
因为要层序遍历就要用到队列，C语言队列代码如下：

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

typedef struct Node* QDataType;
typedef struct QListNode

{
	struct QListNode* next;
	QDataType data;
}QNode;
// 队列的结构 
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;
// 初始化队列 
void QueueInit(Queue* q)
{
	q->tail = NULL;
	q->head = NULL;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		exit(-1);
	}
	else
	{
		newnode->next = NULL;
		newnode->data = data;
		if (q->tail == NULL)
		{
			q->tail = q->head = newnode;
		}
		else
		{
			q->tail->next = newnode;
			q->tail = newnode;
		}
		
	}
}
// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->tail);
	if (q->head->next == NULL)
	{
		free(q->head);
		q->head = q->tail = NULL;
	}
	else
	{
		QNode* next = q->head->next;
		free(q->head);
		q->head = next;
	}
	
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->tail);
	return q->head->data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->tail);
	return q->tail->data;


}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	int n = 0;
	QNode* cur = q->head;
	while (cur)
	{
		n++;
		cur = cur->next;

	}
	return n;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	return q->tail == NULL;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	assert(q->tail);
	QNode* cur = q->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(q);
}

该接口函数代码如下：

struct Node* connect(struct Node* root) {
	Queue p;//创建队列
    QueueInit(&p);//队列初始化
    if(root==NULL)//root为空直接返回NULL
    {
        return  NULL;
    }
    QueuePush(&p,root);//先将root入队列
    int n = 1;//遍历n用来计当前层元素个数
  struct Node** tmp = NULL;//元素为结构体指针的数组
    while(n!=0)//当前层元素为0时，停止循环
    {
        tmp = realloc(tmp,sizeof(struct Node*)*n);//根据每层大小调整数组大小
        int c = 0;//统计下一层个数
        for(int i = 0;i<n;i++)//循环遍历当前层中的元素
        {
            tmp[i] = QueueFront(&p);
            QueuePop(&p);
            if(i+1<n)//如果不为当前层最后一个元素则链接下一个
            {
                (tmp[i])->next = QueueFront(&p);
            }
            if((tmp[i])->left!=NULL)//判断队头元素左右指针指向节点是否为空，不为空则入队列
            {
                QueuePush(&p,(tmp[i])->left);
                c++;
            }
            if((tmp[i])->right!=NULL)
            {
                QueuePush(&p,(tmp[i])->right);
                c++;
            }
        }
        n = c;
        if(n==0)
        {
            free(tmp);
        }
    }
    QueueDestroy(&p);
    return root;//返回根节点
}

时间复杂度o(n) 空间复杂度o(n)
本题进阶要求空间复杂度为o(1),所以下面为大家介绍一种更优化的方法。

二、优化

上面运行效率并不是很高，这是因为我们把节点不同的入队然后再不停的出队，其实可以不需要队列，每一行都可以看成一个链表比如第一行就是只有一个节点的链表，第二行是只有两个节点的链表，以此类推。

如动图所示：
代码如下：

/**
 * 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 NULL;
    }
    struct Node newhead;//哑铃头节点
    newhead.next= root;
    struct Node* tail = &newhead;//用于链表尾插
    struct Node* cur = root;//当前节点
    int flag = 0;//判断是否下层节点是否有元素
while(1)
{
    flag = 0;
   while(cur!=NULL)
    {
       if(cur->left!=NULL)//
       {
           flag = 1;
           tail->next = cur->left;//链接cur的左节点
           tail = tail->next;
       }
        if(cur->right!=NULL)
        {
            flag = 1;
            tail->next = cur->right;//链接cur的右节点
            tail = tail->next;
        }
        cur = cur->next;
    } 
    if(flag == 0)
    {
        return root;
    }
    else
    {
        cur = newhead.next;
        tail = &newhead;
    }
}
return root;
}

时间复杂度o(n) 空间复杂度o(1)

总结

以上就是关于该题的普通解法 和优化解法，希望对大家有所帮助，如有错误希望及时告知。