题目

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

  1. struct Node {
  2.   int val;
  3.   Node *left;
  4.   Node *right;
  5.   Node *next;
  6. }

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

进阶：

  • 你只能使用常量级额外空间。
  • 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

image.png

思路

按照层序遍历的思路来做，使用队列，维护结点入队和出队。

  1. """
  2. # Definition for a Node.
  3. class Node:
  4.     def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
  5.         self.val = val
  6.         self.left = left
  7.         self.right = right
  8.         self.next = next
  9. """
  11. class Solution:
  12.     def connect(self, root: 'Node') -> 'Node':
  13.         if root is None: return 
  14.         ans = []
  15.         queue = [root]
  16.         while len(queue) > 0:
  17.             length = len(queue)
  18.             for i in range(length):
  19.                 node = queue.pop(0)
  21.                 if i != length - 1:
  22.                     node.next = queue[0]
  24.                 if node.left: queue.append(node.left)
  25.                 if node.right: queue.append(node.right)
  26.         return root