class Solution {
public:
queue<Node*>q;
Node* connect(Node* root) {
if(!root) return root;
q.push(root);
int sz;
while(!q.empty())
{
sz=q.size();
Node* n=q.front();
q.pop();
while(sz>0)
{
if(n->left)
{
q.push(n->left);
q.push(n->right);
}
if (sz!=1)
{
n->next=q.front();
q.pop();
n=n->next;
}
--sz;
}
}
return root;
}
};
半个小时。
参考了广度优先遍历。
加油。
class Solution {
public:
Node* connect(Node* root) {
if (root == nullptr) {
return root;
}
// 从根节点开始
Node* leftmost = root;
while (leftmost->left != nullptr) {
// 遍历这一层节点组织成的链表,为下一层的节点更新 next 指针
Node* head = leftmost;
while (head != nullptr) {
// CONNECTION 1
head->left->next = head->right;
// CONNECTION 2
if (head->next != nullptr) {
head->right->next = head->next->left;
}
// 指针向后移动
head = head->next;
}
// 去下一层的最左的节点
leftmost = leftmost->left;
}
return root;
}
};
这个答案好。