LeetCode Algorithm 116. Populating Next Right Pointers in Each Node

5th July 2017 at 10:07am
LeetCodeProblems

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),需要留意这种边界条件。