题目描述
填充每个节点的下一个节点
题目要求我们填充每个节点的 \(next\) 指针,让它指向它的(同一层)右侧的节点,如果没有,指向 $NULL,(初始时全部指向 \(NULL\))。
思路
看到关于二叉树的问题,首先要想到关于二叉树的一些常见遍历方式,
对于二叉树的遍历有:
- 前序遍历
- 中序遍历
- 后序遍历
- 深度优先搜索(DFS)
- 宽度优先搜索(BFS)
除了上面介绍的5种以外,还有 \(Morris\)(莫里斯)的前中后 \(3\) 种遍历方式,总共也就这 \(8\) 种。所以只要遇到二叉树相关的算法题,首先想到的就是上面的几种遍历方式,然后再稍加修改,基本上也就这个套路。
这题让求的就是让把二叉树中每行都串联起来,对于这道题来说最适合的就是 \(BFS\)。也就是一行一行的遍历,如下图所示
代码
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;
Node() : val(0), left(NULL), right(NULL), next(NULL) {}
Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
Node* connect(Node* root) {
if(root == NULL) return NULL;
queue<Node*> q;
q.push(root);
while(q.size())
{
Node *pre = NULL;
int n = q.size();
for(int i = 0; i < n; i ++ ) // 每次遍历一层
{
auto t = q.front(); q.pop();
if(pre) pre->next = t, pre = t;
else pre = t;
if(t->left) q.push(t->left);
if(t->right) q.push(t->right);
}
}
return root;
}
};
标签:Node,遍历,val,--,next,bfs,117,right,NULL
From: https://www.cnblogs.com/ALaterStart/p/16771090.html