2024.5.2 —— LeetCode 高频题复盘

151. 反转字符串中的单词

题目链接

class Solution:def reverseWords(self, s: str) -> str:ls=s.strip().split()ls.reverse()res=" ".join(ls)return res

129. 求根节点到叶节点数字之和

题目链接

# 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 = right
class Solution:def helper(self,root,i):if not root:return 0temp=i*10+root.valif not root.left and not root.right:return tempreturn self.helper(root.left,temp)+self.helper(root.right,temp)def sumNumbers(self, root: Optional[TreeNode]) -> int:return self.helper(root,0)

104. 二叉树的最大深度

题目链接

# 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 = right
class Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:if not root:return 0leftHight=self.maxDepth(root.left)rightHigh=self.maxDepth(root.right)return max(leftHight,rightHigh)+1

101. 对称二叉树

题目链接

# 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 = right
class Solution:def isSymmetric(self, root: Optional[TreeNode]) -> bool:def judge(left,right):if not left and not right:return Trueelif not left or not right:return Falseelif left.val!=right.val:return Falseelse:return judge(left.left,right.right) and judge(left.right,right.left)if not root:return Truereturn judge(root.left,root.right)

110. 平衡二叉树

题目链接

# 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 = right
class Solution:def isBalanced(self, root: Optional[TreeNode]) -> bool:# 二叉树的最大深度def height(root):if not root:return 0return max(height(root.left),height(root.right))+1if not root:return Truereturn abs(height(root.left)-height(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)

144. 二叉树的前序遍历

题目链接

递归

# 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 = right
class Solution:def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:lis=[]def traversal(root):if not root:returnlis.append(root.val)traversal(root.left)traversal(root.right)traversal(root)return lis

非递归

# 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 = right
class Solution:def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:white,gray=0,1stack=[(white,root)]res=[]while stack:color,node=stack.pop()if node is None:continueif color==white:stack.append((white,node.right))stack.append((white,node.left))stack.append((gray,node))else:res.append(node.val)return res

543. 二叉树的直径

题目链接

# 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 = right
class Solution:def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:# 一条路径的长度为该路径经过的节点数减一，# 所以求直径（即求路径长度的最大值）等效于求路径经过节点数的最大值减一self.max=0def depth(root):if not root:return 0left=depth(root.left)right=depth(root.right)self.max=max(self.max,left+right+1)return max(left,right)+1depth(root)return self.max-1

48. 旋转图像

题目链接

class Solution:def rotate(self, matrix: List[List[int]]) -> None:"""Do not return anything, modify matrix in-place instead."""# 用翻转代替旋转# 先水平翻转再主对角线翻转即可得到将图像顺时针旋转90度的图像n=len(matrix)# 水平翻转for i in range(n//2):for j in range(n):matrix[i][j],matrix[n-1-i][j]=matrix[n-1-i][j],matrix[i][j]# 主对角线翻转for i in range(n):for j in range(i):matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]

98. 验证二叉搜索树

题目链接

# 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 = right
class Solution:def isValidBST(self, root: Optional[TreeNode]) -> bool:# 中序遍历:左中右self.pre=Nonedef dfs(root):if not root:return Trueleft=dfs(root.left)if self.pre and self.pre.val>=root.val:return Falseself.pre=rootright=dfs(root.right)return left and rightreturn dfs(root)

39. 组合总和

题目链接

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:path=[]res=[]def backtracking(candidates,s,target,startIndex):if s>target: # 要剪枝必须排序returnif s==target:res.append(path[:])returnfor i in range(startIndex,len(candidates)):s+=candidates[i]path.append(candidates[i])backtracking(candidates,s,target,i) # 下一层i依然可以取到s-=candidates[i]path.pop()candidates.sort()backtracking(candidates,0,target,0)return res