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

类型：树

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

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

  ❓ 给你一个满二叉树（所有叶子节点都在最底层，每个父节点都有两个子节点）。对于每一个结点，请你填充其 next 指针，指向其右侧的结点。右侧没有结点，则置为 null。

  💡 层序遍历

  class Solution:
      def connect(self, root: 'Node') -> 'Node':
          if not root:
              return None
  
          queue = [root]
          while queue:
              newQueue = []
              for i in range(len(queue)):
                  queue[i].next = queue[i + 1] if i + 1 < len(queue) else None
                  if queue[i].left: newQueue.append(queue[i].left)
                  if queue[i].right: newQueue.append(queue[i].right)
              queue = newQueue
  
          return root

  时间复杂度：O(n)，空间复杂度：O(n)

  💡 原地逐层连接

  我们在填写 next 指针时，其实有两种情况。

  • 连接同一个父结点的两个孩子

    

    这种情况，我们直接连接即可。

  • 连接一个父结点的右孩子与另一个父结点的左孩子

    

    这种情况下，由于跨了两个不同的父结点，我们要上一层的 next 连接已经建立好了才好连接。即如下所示：

    

  class Solution:
      def connect(self, root: 'Node') -> 'Node':
  
          if not root:
              return root
  
          # 从根节点开始
          leftmost = root
  
          while leftmost.left:
  
              # 遍历这一层节点组织成的链表，为下一层的节点更新 next 指针
              head = leftmost
              while head:
  
                  # CONNECTION 1
                  head.left.next = head.right
  
                  # CONNECTION 2
                  if head.next:
                      head.right.next = head.next.left
  
                  # 指针向后移动
                  head = head.next
  
              # 去下一层的最左的节点
              leftmost = leftmost.left
  
          return root

  时间复杂度：O(n)，空间复杂度：O(1)