LeetCode #116 #117 2018-08-07

116. Populating Next Right Pointers in Each Node

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/description/

这道题是要将一棵树的每一层维护成一个链表，树本身是给定的。其实思路上很接近层序遍历Binary Tree Level Order Traversal，只是这里不需要额外维护一个队列。因为这里每一层我们会维护成一个链表，这个链表其实就是每层起始的那个队列，因此我们只需要维护一个链表的起始指针就可以依次得到整个队列了。接下来就是有左加左入链表，有右加右入链表，直到链表没有元素了说明到达最底层了。算法的复杂度仍然是对每个结点访问一次，所以是O(n)，而空间上因为不需要额外空间来存储队列了，所以是O(1)。
代码如下：

# Definition for binary tree with next pointer.
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None

class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        cur_head = root
        nxt_head = pre = None
        while cur_head:
            cur = cur_head
            while cur:
                if cur.left:
                    if not nxt_head:
                        nxt_head = cur.left
                        pre = cur.left
                    else:
                        pre.next = cur.left
                        pre = pre.next
                if cur.right:
                    if not nxt_head:
                        nxt_head = cur.right
                        pre = cur.right
                    else:
                        pre.next = cur.right
                        pre = pre.next
                cur = cur.next
            cur_head = nxt_head
            nxt_head = None

做题时的感悟:
做这种题，一定要搞清楚指针的移动，何时清空。不然很有可能出现不循环或者死循环。
在外层循环：只要还有链表，即curHead != None，就要继续循环。
在内层循环：cur从curHead即该链表的头部开始，cur = cur.next循环至该链表结束。循环的同时连接下层链表。
在外层循环：将下层链表头赋值给当前链表头，curHead ＝ nextHead注意，这里还要清空下层链表头指针，即nextHead ＝ None。不然nextHead永远不会更新，就会出现死循环。

117. Populating Next Right Pointers in Each Node II

https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/description/

这道题目的要求和Populating Next Right Pointers in Each Node是一样的，只是这里的二叉树没要求是完全二叉树。其实在实现Populating Next Right Pointers in Each Node的时候我们已经兼容了不是完全二叉树的情况，其实也比较好实现，就是在判断队列结点时判断一下他的左右结点是否存在就可以了。时间复杂度和空间复杂度不变，还是O(n)和O(1)。

代码与Populating Next Right Pointers in Each Node完全相同。