Python|每日一练|树|深度优先搜索|数组|二分查找|链表|双指针|单选记录：填充每个节点的下一个右侧节点指针|搜索插入位置|旋转链表

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: Node"""if 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 <= 100
• 0 <= k <= 2 * 109

选项代码：

class ListNode(object):def __init__(self, x):self.val = xself.next = None
class LinkList:def __init__(self):self.head=Nonedef initList(self, data):self.head = ListNode(data[0])r=self.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: ListNode"""if 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)))