116. Populating Next Right Pointers in Each Node

题目链接 | 我的解答

这个题意很简单，就是给你一棵完美二叉树（perfect binary tree）：

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

其中每个结点都有一个 next 指针，你需要让它指向它同级的右边的结点：

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

要求是只能用常量的额外空间。

做这个题的时候，我陷入了之前二叉树中序遍历的思维惯性，认为整个过程中树的根结点的需要一直保留。但是这道题的关键是拆分、细化问题。其实第一层（1号结点），在做完 2 -> 3 的连接后，就没有作用了。对于第二层也同理（2, 3 号结点），如果 4->5->6->7 做完了，第二层也没有作用了。

因此这道题可以很简单地用非递归或者递归的形式实现。但是留意非递归形式并非常量额外空间的，因为每层递归带来了额外的空间消耗，消耗的空间跟 n 线性相关。

另外有一点，这个树可以是完全空的（root 就是 NULL），需要留意这种边界条件。