和層序遍歷差不多的思路，將節點儲存在隊列里，一邊取出節點一邊放入取出節點的左右節點，直到隊列空。

/*
// 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) {if(root==NULL) return root;int record=1;queue<Node*> n;n.push(root);while(!n.empty()){Node* node=NULL;for(int i=0;i<record;i++){Node* first=n.front();if(first->left){n.push(first->left);n.push(first->right);}if(node) node->next=first;node=first;n.pop();}record*=2;}return root;}
};

本來我是寫的vector，但是發現queue更好，完美匹配。

以及看了答案發現還有一種很機智的思路。

大概就是next有兩種取法（對于root和其left、right），一種是left的next為right，一種是right的next為root的next的left。

如此就可以遞歸。

/*
// 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) {Node* result=root;while(root){Node* record=root->left;while(root&&root->left){root->left->next=root->right;if(root->next) root->right->next=root->next->left;root=root->next;}root=record;}return result;}
};