https://leetcode.com/problems/populating-next-right-pointers-in-each-node/
1.递归
/*
// 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) {connect(root, nullptr);return root;}void connect(Node* root, Node* sib){if(root==nullptr) return;root->next = sib;connect(root->left, root->right);if(sib!=nullptr)connect(root->right, sib->left);elseconnect(root->right, nullptr);}
};2.非递归-双队列法, 在分层遍历基础上进行修改即可。
/*
// 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) {queue<Node*> a, b;if(root!=nullptr){a.push(root);}while(!a.empty() || !b.empty()){while(!a.empty()){Node* first = a.front();a.pop();if(first->left!=nullptr)b.push(first->left);if(first->right!=nullptr)b.push(first->right);if(a.empty())first->next = nullptr;elsefirst->next = a.front();}while(!b.empty()){Node* first = b.front();b.pop();if(first->left!=nullptr)a.push(first->left);if(first->right!=nullptr)a.push(first->right);if(b.empty())first->next = nullptr;elsefirst->next = b.front();}}return root;}
};