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
这道题的关键点在于维系三个 变量：
- curt : the curt root we are passing as the method argument
- first : the first node in the level same as root's children'
- prev : the previous node we just connected to its next node in this level
每次循环要先确定first, 因为每次我们换行都会更新first为null, 所以要首先定下来新的first. 然后我们分别查看curt.left, curt.right, 如果左子树不为空，我们就要把之前刚连接好的node的next指向curt.left. 也就是prev.next = curt.left. 然而要这么做，我们必须先判断curt.left != null， 并且要注意prev == null 和prev != null两种情况。第一种情况说明这一层还没开始连next node, 那么直接设prev = curt.left就好了,；另一种情况就要连接之前连接的最后一个节点和目前的节点，即prev.next = curt.left. 右子树同理。最后连接完左右子树后，要确定curt所在level还有其他节点么,也就是curt.next == null? 如果没有了，则开始下一行的连接，更新curt, first, prev就可以了;如果还有，直接curt = curt.next 接着连接下一个。
/**
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
* int val;
* TreeLinkNode left, right, next;
* TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null){
return;
}
TreeLinkNode curt = root;
//the first node in the level where the children of root are
TreeLinkNode first = null;
//the last node finished connecting to its next in this level
//(the same level as root's childreb).
TreeLinkNode prev = null;
while (curt != null){
if (first == null){
if (curt.left != null){
first = curt.left;
} else if (curt.right != null){
first = curt.right;
}
}
if (curt.left != null){
if (prev != null){
prev.next = curt.left;
}
prev = curt.left;
}
if (curt.right != null){
if (prev != null){
prev.next = curt.right;
}
prev = curt.right;
}
if (curt.next != null){
curt = curt.next;
} else {
curt = first;
prev = null;
first = null;
}
}
}
}
