117. 填充每个节点的下一个右侧节点指针 II

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

解法一：层序

和116题一样的代码

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return root
        queue = [root]
        while queue:
            last = None     #记录同一层前一个结点，初始为空
            for _ in range(len(queue)):
                node = queue.pop(0)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                if last:
                    last.next = node
                last = node
        return root

解法二：递归

注意不能前序，应该先递归处理右子树再左。因为每次处理root时得用到root.next的信息，所以必须先对右侧处理。

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return root
        #若有左子，且有右子，则左子连接右子
      	#无右子，则左子连接父亲右侧的左（或右）子
        if root.left:
            if root.right:
                root.left.next = root.right
            else:
                next = root.next
                while next:
                    if next.left:
                        root.left.next = next.left
                        break
                    if next.right:
                        root.left.next = next.right
                        break
                    next = next.next    #无子则进入下一个
        #若有右子，连接父亲右侧的左（或右）子
        if root.right:
            next = root.next
            while next:
                if next.left:
                    root.right.next = next.left
                    break
                if next.right:
                    root.right.next = next.right
                    break
                next = next.next
        #先递归右子树，再递归左子树   
        root.right = self.connect(root.right)
        root.left = self.connect(root.left)
        return root