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