填充树的next指针ii

题目要求空间复杂度为常数级别，因此不能用递归或者使用队列辅助。

如果当前层中节点的next指针已经填充完毕，那么我们很容易根据当前层去填充下一层，只需要“记住”下一层的最左侧节点，即可通过循环实现题目的目标。在这里引入哑节点记录下一层最左侧节点。

另外的话，由于题中二叉树不是满二叉树或者完全二叉树，需要用一个辅助指针记录上一个节点。

代码如下：

class Solution {
public:
    void connect(TreeLinkNode *root) {
        TreeLinkNode *left = root;
        while (left) {
            TreeLinkNode dummy(0), *prev;
            prev = &dummy;
            for (auto p = left; p; p = p->next) {
                if (p->left) {
                    prev->next = p->left;
                    prev = p->left;
                }
                if (p->right) {
                    prev->next = p->right;
                    prev= p->right;
                }
            }
            left = dummy.next;
        }
    }
};