填充每个节点的下一个右侧节点Ⅱ-力扣

本题如果利用BFS去层序遍历，代码和 填充每个节点的下一个右侧节点 题没有任何区别。但是利用已经建立好的next链表去做，则必要考虑到next指向的节点子节点是否为空的可能。

1. class Solution {
2. public:
3.     Node* connect(Node* root) {
4.         if(root == nullptr){
5.             return nullptr;
6.         }
7.         Node * head = root;
8.         while(head != nullptr){
9.             Node * dummy = new Node(0);
10.             Node * temp = dummy;
11.             
12.             for(Node* cur = head; cur != nullptr; cur = cur->next){
13.                 if(cur->left != nullptr){
14.                     temp->next =cur->left;
15.                     temp = temp->next;
16.                 }
17.                 if(cur->right != nullptr){
18.                     temp->next = cur->right;
19.                     temp = temp->next;
20.                 }
21.             }
22.             head = dummy->next;
23.         }
25.         return root;
26.     }
27. };

复制代码

利用DFS来解决，通过一个数组来纪录每一层的前节点，然后不断更新这个数组。

1. class Solution {
2. public:
3.     void dfs(Node* root, vector<Node*>& vec, int depth){
4.         if(root == nullptr){
5.             return;
6.         }
7.         if(depth >= vec.size()){
8.             vec.push_back(nullptr);
9.         }
10.         if(vec[depth] != nullptr){
11.             vec[depth]->next = root;
12.         }
13.         vec[depth] = root;
14.         dfs(root->left, vec, depth + 1);
15.         dfs(root->right, vec, depth + 1);
16.     }
18.     Node* connect(Node* root) {
19.         vector<Node*> vec;
20.         int depth = 0;
21.         dfs(root, vec, depth);
22.         return root;
23.     }
24. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。