[Leetcode Solution] Populating Next Right Pointers in Each Node

GOOD PROBLEM

Analysis

• Using BFS the problems would be pretty straightforward
• Using two vector to store the current and next searching layer of BFS separative, then all the nodes withing in one layer will stored in a vector. Then do the requirement is simple.
• However BFS will use at least O(square root n) space to store the searching states. The solution with constant space shows following
• Assuming that the current layer of tree is already constructed, then we can get the address of all the nodes in this layer if we know the left most node.
• And we can construct the next layer of node if we know all of the nodes in this layer
• Thus if we have the left most node of this layer, we can construct all the node in next layer.
• This procedure takes constant space and we can iterative execute this procedure until the left most node has no child 

Note

Code

• BFS

• Refined