leetcode 116 117 Populating Next Right Pointers in Each Node II 解题思路记录

Posted on | In ,

面snowflake的时候面到过类似117的题，本身也是高频tree题，记录一下

116. Populating Next Right Pointers in Each Node

这题是 perfect binary tree（Wikipedia: A perfect binary tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level），所以简化了非常多。但是116和117的核心思路是一致的，这题如果不要求我们用constant extra space来做的话，思路就非常简单，寻常的bfs走一遍，生成每个next pointer就行了。但是普通的bfs显然不满足O(1)的空间要求，但是细细体会，next right pointer这个pointer其实可以提供给我们每一行的顺序，当我们要为child level构建next right pointer时，可以使用parent level已生成的pointer来提供bfs所需的信息。

两种实现，recursive或iterative：

1
2
3
4
5
6
7
8
9
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if root and root.left:
            root.left.next = root.right
            if root.next:
                root.right.next = root.next.left
            self.connect(root.left)
            self.connect(root.right)
        return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return None
        cur  = root
        next = root.left

        while cur.left :
            cur.left.next = cur.right
            if cur.next:
                cur.right.next = cur.next.left
                cur = cur.next
            else:
                cur = next
                next = cur.left
        return root

117. Populating Next Right Pointers in Each Node II

这题没有perfect binary tree的条件，所以多了两个需解决的问题：

  • parent.left.next并不一定指向parent.right，同样，parent.right.next也并不一定指向parent.next.left

    A: 判断下呗

  • 当构建完一行的next pointers后，如何寻找下一行的head node

    A: 来一个dummy variable

假设我们已经建完parent行的next pointer，可以把它看成一个单向链表。那么我们需要做的就是，从parent node的head开始 (因为我们建了dummy，所以head就是dummy.next)，遍历parent level。在child level, 新建一个tail变量，初始值为dummy，在遍历parent的node时，不断更新tail，使其总是为已遍历的node的tail。具体实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        tail = dummy = TreeNode()
        cur = root
        while cur:
            for n in (cur.left, cur.right):
                tail.next = n
                if tail.next:
                    tail = tail.next
            cur = cur.next
            if not cur:
                cur, tail = dummy.next, dummy
        return root

另外，为了实现O(1) space，dummy是重复利用的，可能会有点confusing。