Leetcode 117. Populating Next Right Pointers in Each Node II

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

题意：116题的followup，二叉树不在保证是一棵完整二叉树，并且要求只用O(1)的空间复杂度。

思路：
非满二叉树用116题的宽度优先搜索的方法仍然能够解决，但是空间复杂度是O(n)。
O(1)空间复杂度没有想到合适的方法，查看了discuss的解法。
discuss排名最高的解法，思路是用三个指针cur、pre和head：cur指向当前层遍历到的节点，根据cur的left和right，将下一层节点的next连接起来；pre指向下一层遍历到的前一个节点，主要用于连接下一层当前节点和它的前一个节点；head用于记录下一层的第一个节点，用于更新cur。

public void connect(TreeLinkNode root) {
    if (root == null) {
        return;
    }

    TreeLinkNode cur = root;
    TreeLinkNode head = null;
    TreeLinkNode pre = null;

    while (cur != null) {
        while (cur != null) {
            if (cur.left != null) {
                if (pre == null) {
                    head = cur.left;
                    pre = cur.left;
                } else {
                    pre.next = cur.left;
                    pre = pre.next;
                }
            }
            if (cur.right != null) {
                if (pre == null) {
                    head = cur.right;
                    pre = cur.right;
                } else {
                    pre.next = cur.right;
                    pre = pre.next;
                }
            }
            cur = cur.next;
        }

        cur = head;
        //bug 如果head不置为null，会导致死循环
        head = null;
        pre = null;
    }
}