燕郊做网站找谁,网站开发外包哪家好,网站界面设计形考任务,网站设计培训班询题目#xff1a;
给定一个 完美二叉树 #xff0c;其所有叶子节点都在同一层#xff0c;每个父节点都有两个子节点。二叉树定义如下#xff1a;
struct Node {int val;Node *left;Node *right;Node *next;
}
填充它的每个 next 指针#xff0c;让这个指针指向其下一个右…题目
给定一个 完美二叉树 其所有叶子节点都在同一层每个父节点都有两个子节点。二叉树定义如下
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 nextclass 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 nextclass 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)不需要存储额外的节点。
