营销网站的建设流程,辽宁省建设工程信息网专家库怎么入,电商网站建设技术可行性分析,代理记账网站模板1、填充每个节点的下一个右侧节点指针#xff08;树#xff0c;深度优先搜索#xff09;
给定一个 完美二叉树 #xff0c;其所有叶子节点都在同一层#xff0c;每个父节点都有两个子节点。二叉树定义如下#xff1a;
struct Node {
int val;
Node *left;
Node *rig…1、填充每个节点的下一个右侧节点指针树深度优先搜索
给定一个 完美二叉树 其所有叶子节点都在同一层每个父节点都有两个子节点。二叉树定义如下
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点则将 next 指针设置为 NULL。
初始状态下所有 next 指针都被设置为 NULL。 进阶
你只能使用常量级额外空间。使用递归解题也符合要求本题中递归程序占用的栈空间不算做额外的空间复杂度。示例 输入root [1,2,3,4,5,6,7]
输出[1,#,2,3,#,4,5,6,7,#]
解释给定二叉树如图 A 所示你的函数应该填充它的每个 next 指针以指向其下一个右侧节点如图 B 所示。序列化的输出按层序遍历排列同一层节点由 next 指针连接# 标志着每一层的结束。 提示
树中节点的数量少于 4096-1000 node.val 1000
选项代码
class Node(object):def __init__(self, val, left, right, next):self.val valself.left leftself.right rightself.next next
class Solution(object):def connect(self, root)::type root: Node:rtype: Nodeif not root:returnnode [root]while node:l len(node)for n in range(l):cur node.pop(0)if n (l - 1):cur.next node[0]if cur.left:node.append(cur.left)if cur.right:node.append(cur.right)return root
2、搜索插入位置数组二分查找
给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5输出: 2
示例 2:
输入: [1,3,5,6], 2输出: 1
示例 3:
输入: [1,3,5,6], 7输出: 4
示例 4:
输入: [1,3,5,6], 0输出: 0
选项代码
class Solution:def searchInsert(self, nums, target):l, r int(0), len(nums) - 1while l r:mid int((l r) / 2)if nums[mid] target:l mid 1else:r midif nums[l] target:return l 1return l
if __name__ __main__:s Solution()print (s.searchInsert( [1,3,5,6], 7))
3、旋转链表链表双指针
给你一个链表的头节点 head 旋转链表将链表每个节点向右移动 k 个位置。 示例 1 输入head [1,2,3,4,5], k 2输出[4,5,1,2,3]
示例 2 输入head [0,1,2], k 4输出[2,0,1] 提示
链表中节点的数目在范围 [0, 500] 内-100 Node.val 1000 k 2 * 109
选项代码
class ListNode(object):def __init__(self, x):self.val xself.next None
class LinkList:def __init__(self):self.headNonedef initList(self, data):self.head ListNode(data[0])rself.headp self.headfor i in data[1:]:node ListNode(i)p.next nodep p.nextreturn rdef convert_list(self,head):ret []if head None:returnnode headwhile node ! None:ret.append(node.val)node node.nextreturn ret
class Solution(object):def rotateRight(self, head, k)::type head: ListNode:type k: int:rtype: ListNodeif not head or k 0:return headslow fast headlength 1while k and fast.next:fast fast.nextlength 1k - 1if k ! 0:k (k length - 1) % lengthreturn self.rotateRight(head, k)else:while fast.next:fast fast.nextslow slow.nextreturn self.rotate(head, fast, slow)def rotate(self, head, fast, slow):fast.next headhead slow.nextslow.next Nonereturn head
# %%
l LinkList()
list1 [0,1,2]
k 4
l1 l.initList(list1)
s Solution()
print(l.convert_list(s.rotateRight(l1, k)))
