原题地址为：http://oj.leetcode.com/problems/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

题目简而言之就是要按层遍历二叉树，然后加上指向同一层下一个节点的引用。本来没有什么难度，但是题目中常数空间的要求把这题的做法限制的死死的：不能额外建立一个队列，不能用递归。

这个题目最tricky的地方就是当我遍历某一层的时候，已经遍历过并建好链表的上一层本质上就是一个队列！我们只要保存好当前一层的起点，当这一层遍历完成开始遍历下一层的时候，利用这个起点构成的链表进行按层遍历即可。