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,
1
/ \
2 3
/ \ \
4 5 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL

这个题目是LeetCode[Tree]: Populating Next Right Pointers in Each Node的后续，这里的迭代思路与之相同，只有一个地方的差别：由于树有可能是任意的二叉树，因此当获取下一个节点的时，需要用一个循环进行查找。

我的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;
    }
};

LeetCode[Tree]: Populating Next Right Pointers in Each Node II