题目:
给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:
struct Node {int val;Node *left;Node *right;Node *next; }
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL
。
初始状态下,所有 next 指针都被设置为 NULL
。
示例 1:
输入:root = [1,2,3,4,5,6,7] 输出:[1,#,2,3,#,4,5,6,7,#] 解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化的输出按层序遍历排列,同一层节点由 next 指针连接,'#' 标志着每一层的结束。
示例 2:
输入:root = [] 输出:[]
思路(详细分析根节点root):
这道题也套用了二叉树层序遍历的模板,不同的是该题有了next指针,把整个二叉树的同一层级的节点连接起来了
做这道题时我有些迷糊了,对于root到底是什么不太理解
之前 queue = collections.deque([root]) 里root是给定的树的结构里的根节点的值 如:[3,9,20,null,null,15,7]
表示的是二叉树的结构,其中 3
是根节点的值,而 [3,9,20,null,null,15,7]
是根节点及其左右子树的结构。因此,根节点是 3
,而不是 [3,9,20,null,null,15,7]
但是在这道题目里(结合下面代码分析)
当我们在二叉树中使用 `next` 指针时,我们的目标是将同一层级的节点连接起来,形成一个横向的链表结构。因此,在这段代码中,返回的根节点 `root` 包含了整个树的结构,以及每个节点之间通过 `next` 指针连接形成的横向链表。这意味着,根节点 `root` 不仅包含了树的层次结构(每个节点的值、左右子节点),还包含了同一层节点之间的连接关系。
具体来说,在这段代码中,我们通过广度优先搜索(BFS)遍历树的节点,并使用队列 `queue` 来存储每一层的节点。在遍历过程中,对于每个节点,我们首先将其左右子节点加入队列中,然后在同一层的节点之间建立 `next` 指针的连接关系。例如,如果当前节点的左右子节点都存在,那么我们将左子节点的 `next` 指针指向右子节点;如果当前节点是同一层的最后一个节点(即 `i < size - 1`),那么将其 `next` 指针指向队列中的下一个节点。
因此,在这段代码中,返回的根节点 `root` 包含了整个树的结构,以及通过 `next` 指针连接形成的横向链表。这使得我们可以在树的层次结构基础上,通过 `next` 指针快速地访问同一层节点,实现了一种特殊的树的遍历方式。
代码:
层序遍历(广度优先搜索)法
"""
# Definition for a Node.
class Node:def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):self.val = valself.left = leftself.right = rightself.next = next
"""
class Solution:def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':if not root:return rootfrom collections import dequequeue = deque([root]) # 创建一个双端队列,并将根节点放入队列中while queue: # 当队列不为空时循环size = len(queue) # 获取当前队列的长度for i in range(size): # 遍历当前队列中的节点node = queue.popleft() # 从队列中取出一个节点if node.left: # 如果节点有左子节点,则将左子节点放入队列queue.append(node.left)if node.right: # 如果节点有右子节点,则将右子节点放入队列queue.append(node.right)if i < size - 1: # 如果不是当前层的最后一个节点,将当前节点的next指针指向队列中的下一个节点node.next = queue[0]return root # 返回根节点
链表解法 :
"""
# Definition for a Node.
class Node:def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):self.val = valself.left = leftself.right = rightself.next = next
"""
class Solution:def connect(self, root: 'Node') -> 'Node':first = rootwhile first:cur = firstwhile cur: # 遍历每一层的节点if cur.left: cur.left.next = cur.right # 找左节点的nextif cur.right and cur.next: cur.right.next = cur.next.left # 找右节点的nextcur = cur.next # cur同层移动到下一节点first = first.left # 从本层扩展到下一层return root
复杂度分析:
层序遍历(广度优先搜索)法:
- 时间复杂度:O(N),每个节点会被访问一次且只会被访问一次,即从队列中弹出,并建立 next 指针。
- 空间复杂度:O(N),这是一棵完美二叉树,它的最后一个层级包含 N/2 个节点。广度优先遍历的复杂度取决于一个层级上的最大元素数量。这种情况下空间复杂度为 O(N)。
链表解法 :
时间复杂度:O(N),每个节点只访问一次。
空间复杂度:O(1),不需要存储额外的节点。