前言
持续更新了
正文
问题来源
本问题来自leetcode上的117题。
问题描述
给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
示例 1:
分析：
我直接将116的代码直接提交了，后来看到有大佬的算法很简单易懂
思路就是: 在当前层时,把下一层第一个节点用dummy记录下来,然后遍历当前层的时候,把下面一层串起来,当前层遍历完,通过dummy可以开始下一层的遍历(同样重复上述, 将dummy记录下下层第一个节点,然后遍历该层, 并把下面一层串起来)
class Solution {
public:
Node* connect(Node* root) {
Node* curr=root;
Node* dummy=new Node;
while(curr) // 每次到这表示处理完一层
{
Node* tail = dummy;
while (curr) // 遍历当前层的节点,处理下一层
{
if (curr->left) // 下一层
{
tail->next=curr->left;
tail=tail->next;
}
if (curr->right) // 下一层
{
tail->next=curr->right;
tail=tail->next;
}
curr=curr->next;
}
curr=dummy->next; // 指向下一层的开始,继续
if (tail==dummy) break;
}
return root;
}
};
总结：
勤思考。
结语
不管怎么样好好加油。
