题目:
给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:
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 = val
self.left = left
self.right = right
self.next = next
"""
class Solution:
def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
if not root:
return root
from collections import deque
queue = 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 = val
self.left = left
self.right = right
self.next = next
"""
class Solution:
def connect(self, root: 'Node') -> 'Node':
first = root
while first:
cur = first
while cur: # 遍历每一层的节点
if cur.left: cur.left.next = cur.right # 找左节点的next
if cur.right and cur.next: cur.right.next = cur.next.left # 找右节点的next
cur = cur.next # cur同层移动到下一节点
first = first.left # 从本层扩展到下一层
return root
复杂度分析:
层序遍历(广度优先搜索)法:
- 时间复杂度:O(N),每个节点会被访问一次且只会被访问一次,即从队列中弹出,并建立 next 指针。
- 空间复杂度:O(N),这是一棵完美二叉树,它的最后一个层级包含 N/2 个节点。广度优先遍历的复杂度取决于一个层级上的最大元素数量。这种情况下空间复杂度为 O(N)。
链表解法 :
时间复杂度:O(N),每个节点只访问一次。
空间复杂度:O(1),不需要存储额外的节点。