题目描述
给定一个二叉树：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。
初始状态下，所有 next 指针都被设置为 NULL 。
示例 1：
输入：root = [1,2,3,4,5,null,7] 输出：[1,#,2,3,#,4,5,7,#] 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。
示例 2：
输入：root = [] 输出：[]
个人C++解答
GYL
看着灵神的题解写的，自己的话还是写不出递归来，菜就多练
①用DFS，用辅助数组记录深度和左节点，可以理解为每个深度只记录一个左节点，然后查询到右节点的时候让左节点指向右节点，由于开始的时候，所有的next节点均为null那么只需改变存在右边节点的即可。
②用BFS，遍历，将每一层都用next连接起来，但实际写起来感觉也很麻烦，直接复制灵神代码了；
③BFS+链表，依旧是灵神，
DFS
class Solution {
vector<Node*> pre;
public:
Node* connect(Node* root) {
dfs(root,0);
return root;
}
void dfs(Node* node, int depth) {
if(node == nullptr){
return ;
}
if(depth == pre.size()){
pre.push_back(node);
}else{
pre[depth]->next = node;
pre[depth] = node;
}
dfs(node->left,depth+1);
dfs(node->right,depth+1);
}
};
BFS
class Solution {
public:
Node* connect(Node* root) {
if (root == nullptr)
return nullptr;
vector<Node*> q = {root};
while(!q.empty()){
vector<Node*> nxt;
for (int i = 0; i < q.size(); i++) {
Node* node = q[i];
if (i) {
q[i - 1]->next = node;
}
if (node->left) {
nxt.push_back(node->left);
}
if (node->right) {
nxt.push_back(node->right);
}
}
q = move(nxt);
}
return root;
}
};
