【C语言 LeetCode 116】填充每个节点的下一个右侧节点指针
程序员文章站
2022-05-20 21:32:16
...
广度优先搜索(层次遍历)解决填充每个节点的下一个右侧节点指针
- 题目
给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:
struct Node {
int val;
struct Node *left;
struct Node *right;
struct Node *next;
};
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。
初始状态下,所有 next 指针都被设置为 NULL。
- 思路
采用层次遍历依次遍历每一层,当不是该层最后一个结点,将next指针连接到下一个结点;是最后一个结点next指针置NULL。
- 代码
#define max 2500
struct Node* connect(struct Node* root)
{
struct Node *que[max],*p;
int rear=0, front=0, last=1;
if(root)
{
que[rear]=root;
rear = (rear+1)%max;
while(rear!=front)
{
p=que[front];
front = (front+1)%max;
if(p->left)
{
que[rear] = p->left;
rear = (rear+1)%max;
}
if(p->right)
{
que[rear] = p->right;
rear = (rear+1)%max;
}
if(last == front) //判断是否为该层最后一个结点
{
p->next = NULL;
last = rear;
}
else
p->next = que[front]; //连接下一个右侧结点
}
}
return root;
}
上一篇: leetcode144:二叉树的前序遍历
下一篇: 重建二叉树(Python)
推荐阅读
-
C++实现LeetCode(117.每个节点的右向指针之二)
-
填充每个节点的下一个右侧节点指针 II
-
117. 填充每个节点的下一个右侧节点指针 II
-
【C语言 LeetCode 116】填充每个节点的下一个右侧节点指针
-
leetcode116. 填充每个节点的下一个右侧节点指针
-
leetcode117. 填充每个节点的下一个右侧节点指针 II
-
leetcode116. 填充每个节点的下一个右侧节点指针/层次遍历
-
leetcode116. 填充每个节点的下一个右侧节点指针
-
【leetcode】117. 填充每个节点的下一个右侧节点指针 II(populating-next-right-pointers-in-each-node-ii)(bfs)[中等]
-
leetcode116. 填充每个节点的下一个右侧节点指针