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 0
        temp=i*10+root.val
        if not root.left and not root.right:
            return temp
        return 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 0
        leftHight=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 True
            elif not left or not right:
                return False
            elif left.val!=right.val:
                return False
            else:
                return judge(left.left,right.right) and judge(left.right,right.left)
        if not root:
            return True
        return 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 0
            return max(height(root.left),height(root.right))+1
        if not root:
            return True
        return 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:
                return
            lis.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,1
        stack=[(white,root)]
        res=[]
        while stack:
            color,node=stack.pop()
            if node is None:
                continue
            if 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=0
        def depth(root):
            if not root:
                return 0
            left=depth(root.left)
            right=depth(root.right)
            self.max=max(self.max,left+right+1)
            return max(left,right)+1
        depth(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=None
        def dfs(root):
            if not root:
                return True
            left=dfs(root.left)
            if self.pre and self.pre.val>=root.val:
                return False
            self.pre=root
            right=dfs(root.right)
            return left and right
        return 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: # 要剪枝必须排序
                return
            if s==target:
                res.append(path[:])
                return
            for 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