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

一、116. 填充每个节点的下一个右侧节点指针 1.1、题目描述

1.2、题解 1.2.1、层次遍历

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root: return None
        que = [root]
        while que:
            qSize = len(que)
            preNode = None
            for i in range(qSize):
                curNode = que.pop(0)
                if preNode: preNode.next = curNode
                preNode = curNode
                if curNode.left or curNode.right: 
                    que.append(curNode.left)
                    que.append(curNode.right)
        return root

1.2.2、递归

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root: return None

        if 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

二、117. 填充每个节点的下一个右侧节点指针 II 2.1、题目描述

2.2、题解 2.2.1、层次迭代

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root: return None
        que = [root]
        while que:
            qSize = len(que)
            preNode = None
            for i in range(qSize):
                curNode = que.pop(0)
                if preNode: preNode.next = curNode
                preNode = curNode
                if curNode.left:
                    que.append(curNode.left)
                if curNode.right: 
                    que.append(curNode.right)
        return root

2.2.2、递归 2.2.3、常数级空间解法

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        last = root # last始终表示每一层第一个有子树的节点
        while(last):
            while(last and not last.left and not last.right):
                last = last.next
            if not last:
                break # 如果没有左右子树，自然不用更改什么
            pre = None
            cur = last
            while(cur): # 相当于遍历每一层，利用next信息进行递推
                if cur.left:
                    if pre:
                        pre.next = cur.left
                    pre = cur.left
                if cur.right:
                    if pre:
                        pre.next = cur.right
                    pre = cur.right
                cur = cur.next # 找兄弟给右节点

            # 寻找新的一层的第一个节点
            last = last.left if last.left else last.right#由于开始的while循环已经确保last有子树
        return root