本题如果使用BFS去层序遍历，代码和 填充每个节点的下一个右侧节点 题没有任何区别。但是使用已经建立好的next链表去做，则需要考虑到next指向的节点子节点是否为空的可能。
class Solution {
public:Node* connect(Node* root) {if(root == nullptr){return nullptr;}Node * head = root;while(head != nullptr){Node * dummy = new Node(0);Node * temp = dummy;for(Node* cur = head; cur != nullptr; cur = cur->next){if(cur->left != nullptr){temp->next =cur->left;temp = temp->next;}if(cur->right != nullptr){temp->next = cur->right;temp = temp->next;}}head = dummy->next;}return root;}
};
使用DFS来解决，通过一个数组来记录每一层的前节点，然后不断更新这个数组。
class Solution {
public:void dfs(Node* root, vector<Node*>& vec, int depth){if(root == nullptr){return;}if(depth >= vec.size()){vec.push_back(nullptr);}if(vec[depth] != nullptr){vec[depth]->next = root;}vec[depth] = root;dfs(root->left, vec, depth + 1);dfs(root->right, vec, depth + 1);}Node* connect(Node* root) {vector<Node*> vec;int depth = 0;dfs(root, vec, depth);return root;}
};
