Monthly Archives: October 2013

LeetCode: Populating Next Right Pointers in Each Node II constant O(1)空间解法

原题地址为: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的地方就是当我遍历某一层的时候,已经遍历过并建好链表的上一层本质上就是一个队列!我们只要保存好当前一层的起点,当这一层遍历完成开始遍历下一层的时候,利用这个起点构成的链表进行按层遍历即可。