# 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
``````

Tips:

Level order traversal, 见注释

Code:

``````public class Solution {
// Logic:
//        node moves to all nodes in tree in level order fashion
//        needle keeps sewing together next level's children

// levelHead is sentinel, keeps track of start node of next level

while(node != null){ // this loop is for different levels

// needle is sewing next fields in current level
// first time in a level, it is same as leavelHead (with null next)
// but as soon as we get a non null child from node
// needle threads that child into its next,
//      --------->>  thus making that child as next levelHead
//

// this loop moves node in current level
while(node != null){

if(node.left != null){
needle.next = node.left;
needle = needle.next;
}
if(node.right != null){
needle.next = node.right;
needle = needle.next;
}

node = node.next; // move node to next in same level, end up null at rightmost
}
// current level ended in node being null
// take node fom sentinel's next, which is next levels start