Populate next right pointer - 2

Problem:

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

Solution:

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (root == NULL) {
            return;
        }
        queue<TreeLinkNode *> queueTree;
        TreeLinkNode *popedNode;
     
        queueTree.push(root);
     
        while (!queueTree.empty()) {
            popedNode = queueTree.front();
            queueTree.pop();
         
            if (popedNode->left) {
                popedNode->left->next = popedNode->right != NULL ? popedNode->right :
                    getNextRightNode(popedNode->next);
                queueTree.push(popedNode->left);
            }
            if (popedNode->right) {
                popedNode->right->next = getNextRightNode(popedNode->next);
                queueTree.push(popedNode->right);
            }
        }
        return;
    }
 
    TreeLinkNode * getNextRightNode(TreeLinkNode* node) {
        if (node == NULL) {
            return NULL;
        }

        while (node != NULL) {
            if (node->left != NULL) return node->left;
            if (node->right != NULL) return node->right;
            node = node->next;
        }
        return NULL;
    }
};

================ Another attempt =========
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() {}

    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;
        }
       
        vector<Node*> curr, future;
        curr.push_back(root);
        curr.push_back(NULL);
       
        Node *prev = NULL;
        int i = 0;
        while (i < curr.size()) {
            if (prev == NULL) {
                prev = curr[i];
            } else {
                prev -> next = curr[i];
                prev = curr[i];
            }
            if (curr[i] != NULL && curr[i] -> left) {
                future.push_back(curr[i] -> left);
            }
            if (curr[i] != NULL && curr[i] -> right) {
                future.push_back(curr[i] -> right);
            }
            if (i == curr.size() - 1  && future.size() != 0) {
                curr = future;
                curr.push_back(NULL);
                future.clear();
                i = -1;
                prev = NULL;
            }
            i++;
        }
        return root;
    }
};