模拟

这题可以直接操作根节点，我们保存根结点，用作最终返回值。

填充每个结点的 nextnextnext 指针，其实是树的层序遍历。由于 nextnextnext 指针的存在，我们可以做到 O(1)O(1)O(1) 的空间复杂度。

算法:
从根结点出发，利用 nextnextnext 指针同层右移，每个结点的左儿子的 next=next=next= 右儿子，右儿子的 next=next=next= 下一结点的左儿子。

p->left->next = p->right;//左儿子的 next=右儿子
p->right->next = p->next->left;//右儿子的 next=下一结点的左儿子

一层遍历结束后， rootrootroot 走到左儿子，进入下一层遍历。

class Solution {
public:Node* connect(Node* root) {if(!root) return root;Node *temp = root;while(root->left){for(auto p = root;p;p = p ->next){p->left->next = p->right;if(p->next) p->right->next = p->next->left;}root = root->left;}return temp;}
};

1. 时间复杂度 : O(n)O(n)O(n) ， nnn 是结点个数 ，每个结点至多被遍历一次，时间复杂度 O(n)O(n)O(n) 。
2. 空间复杂度 : O(1)O(1)O(1) ， 只使用常量级空间 。

AC