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,

After calling your function, the tree should look like:

我的C++代码实现如下：

class Solution {
public:
    void connect(TreeLinkNode *root) {
        for (TreeLinkNode *levelFirstNode = root; levelFirstNode != nullptr; levelFirstNode = getNext(levelFirstNode)) {
            for (TreeLinkNode *curNode = levelFirstNode; curNode != nullptr; curNode = curNode->next) {
                if (curNode->left) curNode->left->next = curNode->right ? curNode->right : getNext(curNode->next);
                if (curNode->right) curNode->right->next = getNext(curNode->next);
            }
        }
    }

private:
    TreeLinkNode *getNext(TreeLinkNode *node) {
        while (node) {
            if (node->left) return node->left;
            if (node->right) return node->right;
            node = node->next;
        }

        return nullptr;
    }
};

其中，getNext函数获取的是从当前节点开始的下一层的第一个节点。但是这种算法的时间性能表现非常不好（如下图所示），希望发掘更好更快的算法来解决这个问题。