Leetcode刷题日记12（111-120）

问题1：

问题链接：

111. 二叉树的最小深度

问题描述：

给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明：叶子节点是指没有子节点的节点。

实例：

代码：

# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defminDepth(self,root:Optional[TreeNode])->int:#1.从底层向上，递归ifrootisNone:return0ifroot.rightisNone:returnself.minDepth(root.left)+1ifroot.leftisNone:returnself.minDepth(root.right)+1returnmin(self.minDepth(root.left),self.minDepth(root.right))+1

# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defminDepth(self,root:Optional[TreeNode])->int:#2.从顶向下ans=infdefdfs(node:Optional[TreeNode],cnt:int)->None:ifnodeisNone:returncnt+=1ifnode.leftisNoneandnode.rightisNone:nonlocalans ans=min(ans,cnt)returndfs(node.left,cnt)dfs(node.right,cnt)dfs(root,0)returnansifrootelse0

问题2：

问题链接：

112. 路径总和

问题描述：

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。 叶子节点 是指没有子节点的节点。

实例：

代码：

# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defhasPathSum(self,root:Optional[TreeNode],targetSum:int)->bool:ifrootisNone:returnFalsetargetSum-=root.valifroot.leftisNoneandroot.rightisNone:returntargetSum==0returnself.hasPathSum(root.left,targetSum)orself.hasPathSum(root.right,targetSum)

问题3：

问题链接：

113. 路径总和 II

问题描述：

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。

实例：

代码：

# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defpathSum(self,root:Optional[TreeNode],targetSum:int)->List[List[int]]:#利用先序遍历：实现根、左、右res,path=[],[]defrecur(root,tar):ifnotroot:returnpath.append(root.val)tar-=root.valiftar==0andnotroot.leftandnotroot.right:res.append(list(path))recur(root.left,tar)recur(root.right,tar)path.pop()#向上回溯recur(root,targetSum)returnres

问题4：

问题链接：

114. 二叉树展开为链表

问题描述：

给你二叉树的根结点 root ，请你将它展开为一个单链表： 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。 展开后的单链表应该与二叉树 先序遍历 顺序相同。

实例：

代码：

classSolution:defflatten(self,root:Optional[TreeNode])->Optional[TreeNode]:ifrootisNone:returnNoneleft_tail=self.flatten(root.left)right_tail=self.flatten(root.right)ifleft_tail:left_tail.right=root.right# 左子树链表 -> 右子树链表root.right=root.left# 当前节点 -> 左右子树合并后的链表root.left=Nonereturnright_tailorleft_tailorroot

问题5：

问题链接：

115. 不同的子序列

问题描述：

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。 测试用例保证结果在32位有符号整数范围内。

实例：

示例1： 输入：s="rabbbit",t="rabbit" 输出：3解释： 如下所示,有3种可以从 s 中得到 "rabbit" 的方案。 rabbbit rabbbit rabbbit 示例2： 输入：s="babgbag",t="bag" 输出：5解释： 如下所示,有5种可以从 s 中得到 "bag" 的方案。 babgbag babgbag babgbag babgbag babgbag

代码：

classSolution:defnumDistinct(self,s:str,t:str)->int:@cache# 缓存装饰器，避免重复计算 dfs 的结果（一行代码实现记忆化）defdfs(i:int,j:int)->int:ifi<j:return0ifj<0:return1res=dfs(i-1,j)# 删除 s[i]ifs[i]==t[j]:res+=dfs(i-1,j-1)# 不删 s[i]，和 t[j] 匹配returnresreturndfs(len(s)-1,len(t)-1)

classSolution:defnumDistinct(self,s:str,t:str)->int:n,m=len(s),len(t)ifn<m:return0f=[[1]+[0]*mfor_inrange(n+1)]fori,xinenumerate(s):forjinrange(max(m-n+i,0),min(i+1,m)):f[i+1][j+1]=f[i][j+1]ifx==t[j]:f[i+1][j+1]+=f[i][j]returnf[n][m]

问题6：

问题链接：

116. 填充每个节点的下一个右侧节点指针

问题描述：

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下： struct Node{int val;Node*left;Node*right;Node*next;}填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。 初始状态下，所有 next 指针都被设置为 NULL。

实例：

代码：

""" # 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 """classSolution:defconnect(self,root:'Optional[Node]')->'Optional[Node]':#3.BFS+链表cur=rootwhilecur:nxt=dummy=Node()whilecur:ifcur.left:nxt.next=cur.left# 下一层的相邻节点连起来nxt=cur.leftifcur.right:nxt.next=cur.right# 下一层的相邻节点连起来nxt=cur.right cur=cur.next#当前层链表的下一个节点cur=dummy.next#下一层链表的头节点returnroot

""" # 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 """classSolution:defconnect(self,root:'Optional[Node]')->'Optional[Node]':#1.DFSpre=[]defdfs(node:'Node',depth:int)->None:ifnodeisNone:returnifdepth==len(pre):#node是这一层的最左边的节点pre.append(node)else:#pre[depth]是node左边的节点pre[depth].next=node#这里是是让next指向右边那个元素pre[depth]=node#这里是更新数组dfs(node.left,depth+1)dfs(node.right,depth+1)dfs(root,0)#根节点深度为0returnroot

""" # 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 """classSolution:defconnect(self,root:'Optional[Node]')->'Optional[Node]':#2.BFSifrootisNone:returnNoneq=[root]whileq:#pairwise它表示的是一个迭代器（有点废话，itertools里面都是各种迭代器），他的含义是，从对象中获取连续的重叠对。forx,yinpairwise(q):x.next=y temp=q q=[]fornodeintemp:ifnode.left:q.append(node.left)ifnode.right:q.append(node.right)returnroot

问题7：

问题链接：

117. 填充每个节点的下一个右侧节点指针 II

问题描述：

给定一个二叉树： struct Node{int val;Node*left;Node*right;Node*next;}填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。 初始状态下，所有 next 指针都被设置为 NULL 。

实例：

代码：

""" # 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 """classSolution:defconnect(self,root:'Node')->'Node':cur=rootwhilecur:nxt=dummy=Node()# 下一层的链表whilecur:# 遍历当前层的链表ifcur.left:nxt.next=cur.left# 下一层的相邻节点连起来nxt=cur.leftifcur.right:nxt.next=cur.right# 下一层的相邻节点连起来nxt=cur.right cur=cur.next# 当前层链表的下一个节点cur=dummy.next# 下一层链表的头节点returnroot

""" # 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 """classSolution:defconnect(self,root:'Node')->'Node':#2.BFSifrootisNone:returnNoneq=[root]whileq:# 从左到右依次连接forx,yinpairwise(q):x.next=y# 准备下一层的节点tmp=q q=[]fornodeintmp:ifnode.left:q.append(node.left)ifnode.right:q.append(node.right)returnroot

""" # 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 """classSolution:defconnect(self,root:'Node')->'Node':ifrootisNone:returnNoneq=[root]whileq:# 从左到右依次连接forx,yinpairwise(q):x.next=y# 准备下一层的节点tmp=q q=[]fornodeintmp:ifnode.left:q.append(node.left)ifnode.right:q.append(node.right)returnroot

问题8：

问题链接：

118. 杨辉三角

问题描述：

实例：

示例1:输入:numRows=5输出:[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]示例2:输入:numRows=1输出:[[1]]

代码：

classSolution:defgenerate(self,numRows:int)->List[List[int]]:c=[[1]*(i+1)foriinrange(numRows)]foriinrange(2,numRows):forjinrange(1,i):c[i][j]=c[i-1][j-1]+c[i-1][j]returnc

问题9：

问题链接：

119. 杨辉三角 II

问题描述：

实例：

示例1:输入:rowIndex=3输出:[1,3,3,1]示例2:输入:rowIndex=0输出:[1]示例3:输入:rowIndex=1输出:[1,1]

代码：

MX=34c=[[1]*(i+1)foriinrange(MX)]foriinrange(2,MX):forjinrange(1,i):# 左上方的数 + 正上方的数c[i][j]=c[i-1][j-1]+c[i-1][j]classSolution:defgetRow(self,rowIndex:int)->List[int]:returnc[rowIndex]

问题10：

问题链接：

120. 三角形最小路径和

问题描述：

给定一个三角形 triangle ，找出自顶向下的最小路径和。 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标+1的两个结点。也就是说，如果正位于当前行的下标i，那么下一步可以移动到下一行的下标i或i+1。

实例：

示例1： 输入：triangle=[[2],[3,4],[6,5,7],[4,1,8,3]]输出：11解释：如下面简图所示：2346574183自顶向下的最小路径和为11（即，2+3+5+1=11）。 示例2： 输入：triangle=[[-10]]输出：-10

代码：

classSolution:defminimumTotal(self,triangle:List[List[int]])->int:n=len(triangle)@cachedefdfs(i:int,j:int)->int:ifi==n-1:returntriangle[i][j]returnmin(dfs(i+1,j),dfs(i+1,j+1))+triangle[i][j]returndfs(0,0)

classSolution:defminimumTotal(self,triangle:List[List[int]])->int:n=len(triangle)f=[[0]*(i+1)foriinrange(n)]f[-1]=triangle[-1]foriinrange(n-2,-1,-1):forj,xinenumerate(triangle[i]):f[i][j]=min(f[i+1][j],f[i+1][j+1])+xreturnf[0][0]