class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> Q;
        Node* cur;
        if(root) Q.push(root);
        while(!Q.empty()) {
            int sz = Q.size();
            Node* pre = NULL;
            for(int i=0; i<sz; i++) {
                cur = Q.front(); Q.pop();
                if(cur->left) Q.push(cur->left);
                if(cur->right) Q.push(cur->right);
                if(pre) pre->next = cur;
                pre = cur;
            }
        }
        return root;
    }
};