117. Populating Next Right Pointers in Each Node II

Loading...LeetCode

做 116 的时候写得很 generalized，以至于代码可以一个字不改直接 submit 这题...说明做116的时候读题不够认真！漏了简化条件！

116. Populating Next Right Pointers in Each Node

再多写个方法。

拿BFS做层序遍历的原因是需要获取层的开头和结尾，但因为我们是从root(next = None)开始的，直接就可以获取下一个 child node 是第二层的开头，同理，再次 next = None 的时候，下一个就是第三层的开头，就重置 begin 指针，跑新的一层。

利用这个思路，可以用 prev, cur 两个指针遍历整个tree，挨个指定next，不需要再存储整层的数据，所以空间复杂度缩到O(1).

BFS层序遍历

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root: return None
        
        q = collections.deque([root])
        while q:
            width = len(q)
            nextLevel = []
            for _ in range(width):
                node = q.popleft()
                node.next = q[0] if q else None
                if node.left: nextLevel.append(node.left)
                if node.right: nextLevel.append(node.right)
            q.extend(nextLevel)
            
        return root

prev, cur 双指针

class Solution:
    def __init__(self):
        self.begin = None
        self.prev = None
    
    def getNext(self, cur):
        if cur:
            # if there is *prev*, link the previous to current node
            if self.prev: 
                self.prev.next = cur
            # when the *prev* is None, it means we are in the begining of the level
            else: 
                self.begin = cur
            self.prev = cur
        return

    def connect(self, root: 'Node') -> 'Node':
        if not root: return None
        # initialize the level beginning to root (1st level)
        self.begin = root
        
        # for each new level, reset the pointers
        while self.begin:
            # *begin* pointer >>> beginning of next level
            self.prev, cur, self.begin = None, self.begin, None
            # populate each node in the level
            while cur:
                self.getNext(cur.left)
                self.getNext(cur.right)
                cur = cur.next
        return root