LeetCode Hot 100 题解合集

 1class Solution:
 2    def twoSum(self, nums: List[int], target: int) -> List[int]:
 3        hash_map={}
 4        #查询complement是否存在于hash_map中，若不存在，则将nums[i]插入hash_map
 5        for i in range(len(nums)):
 6            complement=target-nums[i]
 7            if complement in hashmap:
 8                return [i,hashmap[complement]]
 9            hash_map[nums[i]]=i
10        return []

 1class Solution:
 2    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
 3		# 创建一个defaultdict对象，默认值为空列表
 4        hashmap = defaultdict(list)
 5        
 6        for word in strs:
 7            # 对每个单词进行排序，作为哈希表的key
 8            sortedWord = "".join(sorted(word))
 9            # 将未排序的单词加入到对应的key的列表中
10            hashmap[sortedWord].append(word)
11        
12        # 直接返回哈希表中所有value的列表
13        return list(hashmap.values())

 1class Solution:
 2    def longestConsecutive(self, nums):
 3        if not nums:
 4            # 如果输入列表为空，直接返回0
 5            return 0
 6        
 7        # 创建一个哈希表，用于记录每个数所在序列的长度
 8        num_dict = {}
 9        max_length = 0
10
11        # 遍历数组中的每个数
12        for num in nums:
13            if num in num_dict:
14                # 如果当前数已经在哈希表中，跳过（避免重复计算）
15                continue
16            
17            # 获取当前数左边和右边相邻数的连续序列长度
18            left = num_dict.get(num - 1, 0)
19            right = num_dict.get(num + 1, 0)
20
21            # 当前数所在连续序列的总长度
22            cur_length = left + right + 1
23            
24            # 更新最大长度
25            max_length = max(max_length, cur_length)
26            
27            # 更新当前数及其连续序列两端点的长度信息
28            num_dict[num] = cur_length
29            num_dict[num - left] = cur_length
30            num_dict[num + right] = cur_length
31
32        # 返回最长的连续序列长度
33        return max_length

 1class Solution:
 2    def moveZeroes(self, nums: List[int]) -> None:
 3        zeroindex=-1
 4        for i in range(len(nums)):
 5            if nums[i]==0 and zeroindex==-1:
 6                zeroindex=i
 7            elif nums[i]!=0 and zeroindex!=-1:
 8                nums[zeroindex],nums[i]=nums[i],nums[zeroindex]
 9                zeroindex+=1
10        return nums

 1class Solution:
 2    def maxArea(self, height: List[int]) -> int:
 3        start, end = 0, len(height) - 1
 4        max_volume = 0
 5
 6        while start < end:
 7            volume = min(height[start], height[end]) * (end - start)
 8            max_volume = max(max_volume, volume)
 9
10            if height[start] < height[end]:
11                start += 1
12            else:
13                end -= 1
14
15        return max_volume

 1class Solution:
 2    def threeSum(self, nums: List[int]) -> List[List[int]]:
 3        if len(nums) < 3: return []
 4        nums.sort()
 5        result = []
 6        
 7        for i in range(len(nums)):
 8            if nums[i] > 0: break
 9            if i > 0 and nums[i] == nums[i - 1]: continue
10            
11            L, R = i + 1, len(nums) - 1
12            while L < R:
13                total = nums[i] + nums[L] + nums[R]
14                if total == 0:
15                    result.append([nums[i], nums[L], nums[R]])
16                    while L < R and nums[L] == nums[L + 1]:
17                        L += 1
18                    while L < R and nums[R] == nums[R - 1]:
19                        R -= 1
20                    L += 1
21                    R -= 1
22                elif total < 0:
23                    L += 1
24                else:
25                    R -= 1
26        
27        return result

 1class Solution:
 2    def lengthOfLongestSubstring(self, s: str) -> int:
 3        if not s:
 4            return 0
 5        
 6        # 初始化指针和结果变量
 7        start, max_length = 0, 0
 8        char_index_map = {}  # 用于存储字符及其最后出现的位置
 9
10        for end in range(len(s)):
11            if s[end] in char_index_map and char_index_map[s[end]] >= start:
12                # 如果当前字符已经存在于字典中且其索引在start之后或等于start，说明有重复字符，
13                # 需要移动start指针，以排除重复字符
14                start = char_index_map[s[end]] + 1
15            
16            # 更新字符的最新索引位置
17            char_index_map[s[end]] = end
18            
19            # 更新最长无重复子串的长度
20            max_length = max(max_length, end - start + 1)
21
22        return max_length

 1class Solution:
 2    def findAnagrams(self, s: str, p: str) -> List[int]:
 3        # 初始化 p 的字符计数器和滑动窗口的字符计数器
 4        p_count = Counter(p)
 5        s_count = Counter(s[:len(p)-1])
 6        
 7        result = []
 8        # 遍历字符串 s，从索引 len(p)-1 到 len(s)-1
 9        #窗口头指针:i-len(p)+1
10        #窗口尾指针:i
11        for i in range(len(p)-1, len(s)):
12            # 将新的字符加入当前滑动窗口的计数器中
13            s_count[s[i]] += 1
14            
15            # 如果当前窗口的字符计数器与 p 的字符计数器相同，则记录起始索引
16            if s_count == p_count:
17                result.append(i - len(p) + 1)
18            
19            # 移除当前窗口左侧即将滑出字符的计数
20            s_count[s[i - len(p) + 1]] -= 1
21            # 如果某个字符的计数变为零，将其从计数器中删除
22            if s_count[s[i - len(p) + 1]] == 0:
23                del s_count[s[i - len(p) + 1]]
24        
25        return result

 1class Solution:
 2    def subarraySum(self, nums: List[int], k: int) -> int:
 3        prefix_sum = 0  # 初始化前缀和
 4        prefix_sum_count = {0: 1}  # 初始化哈希表，包含前缀和为0的情况
 5        count = 0  # 初始化计数器
 6        
 7        for num in nums:
 8            prefix_sum += num  # 更新当前前缀和
 9            count += prefix_sum_count.get(prefix_sum - k, 0)  # 如果存在符合条件的前缀和，则增加计数
10            prefix_sum_count[prefix_sum] = prefix_sum_count.get(prefix_sum, 0) + 1  # 更新当前前缀和出现次数
11                
12        return count  # 返回计数结果

 1class Solution:
 2    def maxSubArray(self, nums: List[int]) -> int:
 3        # 初始化当前子数组和和最大子数组和为第一个元素
 4        current_sum = max_sum = nums[0]
 5        
 6        # 从第二个元素开始遍历数组
 7        for num in nums[1:]:
 8            # 当前子数组和的计算
 9            current_sum = max(num, current_sum + num)
10            # 更新全局最大和
11            max_sum = max(max_sum, current_sum)
12        
13        return max_sum

 1class Solution:
 2    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
 3        # 按起始值排序区间
 4        intervals.sort(key=lambda x: x[0])
 5        merged_intervals = []
 6        
 7        for current in intervals:
 8            if not merged_intervals or merged_intervals[-1][1] < current[0]:
 9                merged_intervals.append(current)
10            else:
11                merged_intervals[-1][1] = max(merged_intervals[-1][1], current[1])
12        
13        return merged_intervals

1class Solution:
2    def rotate(self, nums: List[int], k: int) -> None:
3        n = len(nums)
4        k = k % n  # 防止 k 超过数组长度
5        nums[:] = nums[-k:] + nums[:-k]

 1class Solution:
 2    def rotate(self, nums: List[int], k: int) -> None:
 3        n = len(nums)
 4        k = k % n  # 防止 k 超过数组长度
 5        
 6        def reverse(start: int, end: int) -> None:
 7            while start < end:
 8                nums[start], nums[end] = nums[end], nums[start]
 9                start += 1
10                end -= 1
11
12        reverse(0, n - 1)
13        reverse(0, k - 1)
14        reverse(k, n - 1)

 1class Solution:
 2    def productExceptSelf(self, nums: List[int]) -> List[int]:
 3        n = len(nums)
 4        answer = [1] * n  # 初始化结果数组，全1
 5        # 计算前缀积并存储在 answer 中
 6        for i in range(1, n):
 7            answer[i] = answer[i - 1] * nums[i - 1]
 8            
 9        suffix_product = 1  # 初始化后缀积为1
10        # 计算后缀积，并直接更新 answer
11        for i in range(n - 1, -1, -1):  # 从后往前遍历数组
12            answer[i] *= suffix_product  # 将当前后缀积乘以 answer 中对应位置的值
13            suffix_product *= nums[i]  # 更新后缀积
14        
15        return answer

 1class Solution:
 2    def setZeroes(self, matrix: List[List[int]]) -> None:
 3        m, n = len(matrix), len(matrix[0])
 4        
 5        # 检查第一行是否有0
 6        first_row_has_zero = any(matrix[0][j] == 0 for j in range(n))
 7        # 检查第一列是否有0
 8        first_col_has_zero = any(matrix[i][0] == 0 for i in range(m))
 9        
10        # 使用第一行和第一列作为标记
11        for i in range(1, m):
12            for j in range(1, n):
13                if matrix[i][j] == 0:
14                    matrix[i][0] = 0  # 标记第i行需要变为0
15                    matrix[0][j] = 0  # 标记第j列需要变为0
16        
17        # 根据标记设置0
18        for i in range(1, m):
19            for j in range(1, n):
20                if matrix[i][0] == 0 or matrix[0][j] == 0:
21                    matrix[i][j] = 0
22        
23        # 处理第一行，如果第一行原来存在0，则将第一行全部变为0
24        if first_row_has_zero:
25            for j in range(n):
26                matrix[0][j] = 0
27        
28        # 处理第一列，如果第一列原来存在0，则将第一列全部变为0
29        if first_col_has_zero:
30            for i in range(m):
31                matrix[i][0] = 0

 1class Solution:
 2    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
 3        if not matrix or not matrix[0]:
 4            return []
 5        
 6        m, n = len(matrix), len(matrix[0])
 7        top, bottom, left, right = 0, m - 1, 0, n - 1
 8        result = []
 9        
10        while top <= bottom and left <= right:
11            # 从左到右遍历顶部行
12            for i in range(left, right + 1):
13                result.append(matrix[top][i])
14            top += 1  # 顶部行已遍历，下移一行
15            
16            # 从上到下遍历右侧列
17            for i in range(top, bottom + 1):
18                result.append(matrix[i][right])
19            right -= 1  # 右侧列已遍历，左移一列
20            
21            # 检查是否还有剩余的行和列
22            if top <= bottom:
23                # 从右到左遍历底部行
24                for i in range(right, left - 1, -1):
25                    result.append(matrix[bottom][i])
26                bottom -= 1  # 底部行已遍历，上移一行
27            
28            if left <= right:
29                # 从下到上遍历左侧列
30                for i in range(bottom, top - 1, -1):
31                    result.append(matrix[i][left])
32                left += 1  # 左侧列已遍历，右移一列
33        
34        return result

 1class Solution:
 2    def rotate(self, matrix: List[List[int]]) -> None:
 3        n = len(matrix)
 4        
 5        # 逐层旋转
 6        for layer in range(n // 2):
 7            # 当前层的边界
 8            top, bottom = layer, n - 1 - layer
 9            
10            for i in range(top, bottom):
11                # 计算偏移量
12                offset = i - top
13                
14                # 顺时针旋转四个位置
15                
16                # 保存上边元素
17                temp = matrix[top][i]
18                # 左 -> 上
19                matrix[top][i] = matrix[bottom - offset][top]
20                # 下 -> 左
21                matrix[bottom - offset][top] = matrix[bottom][bottom - offset]
22                # 右 -> 下
23                matrix[bottom][bottom - offset] = matrix[i][bottom]
24                # 上 -> 右
25                matrix[i][bottom] = temp

 1class Solution:
 2    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
 3        # 获取矩阵的行数和列数
 4        if not matrix or not matrix[0]:
 5            return False
 6        rows, cols = len(matrix), len(matrix[0])
 7        
 8        # 从右上角开始
 9        row, col = 0, cols - 1
10        
11        while row < rows and col >= 0:
12            if matrix[row][col] == target:
13                return True
14            elif matrix[row][col] > target:
15                # 如果当前元素比目标大，向左移动
16                col -= 1
17            else:
18                # 如果当前元素比目标小，向下移动
19                row += 1
20        
21        return False

1class Solution: 
2	def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]: 
3		indexA, indexB = headA, headB 
4		while indexA != indexB: 
5			indexA = indexA.next if indexA else headB 
6			indexB = indexB.next if indexB else headA 
7		return indexA

 1class Solution:
 2    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
 3        if not head:
 4            return None
 5        # 初始化前驱节点和当前节点
 6        prev = None
 7        current = head
 8        # 遍历链表，反转指针
 9        while current:
10            next_node = current.next
11            # 反转指针
12            current.next = prev
13            # 移动前驱节点和当前节点
14            prev = current
15            current = next_node
16        
17        # 返回新的头节点（即原链表的最后一个节点）
18        return prev

 1class Solution:
 2    def isPalindrome(self, head: Optional[ListNode]) -> bool:
 3        if not head or not head.next:
 4            return True
 5        # 步骤一：使用快慢指针寻找到链表中间位置
 6        slow, fast = head, head
 7        while fast and fast.next:
 8            slow = slow.next
 9            fast = fast.next.next
10        # 步骤二：对于链表后半部分进行反转
11        def reverseLink(head):
12            prev = None
13            current = head
14            while current:
15                next_node = current.next
16                current.next = prev
17                prev = current
18                current = next_node
19            return prev
20        slow = reverseLink(slow)
21        # 步骤三：判断是否为回文链表
22        while slow:
23            if slow.val != head.val:
24                return False
25            slow, head = slow.next, head.next
26        return True

 1class Solution:
 2  def hasCycle(self, head: Optional[ListNode]) -> bool:
 3    if not head:
 4      return False
 5    slow, fast=head, head
 6    while slow and fast and fast.next:
 7      slow, fast=slow.next, fast.next.next
 8      if slow==fast:
 9        return True  
10    return False

 1class Solution:
 2    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
 3        # 创建一个哑节点作为合并后链表的头节点的前驱节点
 4        dummy = ListNode(-1)
 5        current = dummy
 6        
 7        # 当两个链表都不为空时，进行迭代合并
 8        while list1 and list2:
 9            if list1.val <= list2.val:
10                # 如果list1的值较小或相等，将其节点接入合并链表
11                current.next = list1
12                list1 = list1.next
13            else:
14                # 如果list2的值较小，将其节点接入合并链表
15                current.next = list2
16                list2 = list2.next
17            # 移动当前指针到合并链表的最后一个节点
18            current = current.next
19        
20        # 将未遍历完的链表直接接入合并链表的末尾
21        current.next = list1 if list1 else list2
22        
23        # 返回合并后的链表头节点
24        return dummy.next

 1class Solution:
 2    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
 3        if not head or not head.next:
 4            return None
 5
 6        slow = head
 7        fast = head
 8
 9        # 检测是否有环
10        while fast and fast.next:
11            slow = slow.next
12            fast = fast.next.next
13            if slow == fast:
14                break
15        else:
16            return None
17
18        # 找到环的起始节点
19        slow = head
20        while slow != fast:
21            slow = slow.next
22            fast = fast.next
23
24        return slow

 1class Solution:
 2    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
 3        # 创建虚拟头节点，用于简化链表操作
 4        dummy = ListNode(0)
 5        current = dummy
 6        carry = 0
 7
 8        # 遍历两个链表，直到两者都为空
 9        while l1 or l2:
10            # 计算当前位的和，考虑进位
11            sum_val = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
12            carry = sum_val // 10  # 更新进位
13            current.next = ListNode(sum_val % 10)  # 创建新节点，存储当前位的值
14            current = current.next  # 移动 current 指针到新节点
15
16            # 移动 l1 和 l2 指针到下一个节点
17            if l1:
18                l1 = l1.next
19            if l2:
20                l2 = l2.next
21
22        # 如果最后有进位，需要在结果链表的末尾新增一个节点
23        if carry > 0:
24            current.next = ListNode(carry)
25
26        # 返回结果链表的头节点，即虚拟头节点的下一个节点
27        return dummy.next

 1class Solution:
 2    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
 3        # 创建虚拟头结点，简化边界条件处理
 4        dummy = ListNode(0, head)
 5        
 6        # 初始化快慢指针
 7        fast = slow = dummy
 8        
 9        # 移动快指针 n 步
10        for _ in range(n):
11            fast = fast.next
12        
13        # 同时移动两个指针，直到快指针到达链表末尾
14        while fast.next:
15            fast = fast.next
16            slow = slow.next
17        
18        # 删除结点
19        slow.next = slow.next.next
20        
21        # 返回新的头结点
22        return dummy.next

 1class Solution:
 2    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
 3        # 创建虚拟头节点，方便处理链表头部的交换
 4        dummy = ListNode(0)
 5        dummy.next = head
 6        prev = dummy
 7        
 8        while head and head.next:
 9            # 定义需要交换的两个节点
10            first = head
11            second = head.next
12            
13            # 交换节点
14            # 1. 将 prev 的 next 指向 second
15            prev.next = second
16            # 2. 将 first 的 next 指向 second 的 next
17            first.next = second.next
18            # 3. 将 second 的 next 指向 first
19            second.next = first
20            
21            # 更新指针，准备处理下一对节点
22            prev = first
23            head = first.next
24        
25        # 返回新的链表头节点
26        return dummy.next

 1class Solution:
 2    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
 3        if not head or not head.next:
 4            return head
 5        
 6        # 找到链表的中间节点
 7        def find_mid(head: ListNode) -> ListNode:
 8            slow, fast = head, head.next
 9            while fast and fast.next:
10                slow = slow.next
11                fast = fast.next.next
12            return slow
13        
14        # 合并两个有序链表
15        def merge(l1: ListNode, l2: ListNode) -> ListNode:
16            dummy = ListNode()
17            current = dummy
18            while l1 and l2:
19                if l1.val < l2.val:
20                    current.next = l1
21                    l1 = l1.next
22                else:
23                    current.next = l2
24                    l2 = l2.next
25                current = current.next
26            if l1:
27                current.next = l1
28            if l2:
29                current.next = l2
30            return dummy.next
31        
32        # 找到中间节点并分割链表
33        mid = find_mid(head)
34        right = mid.next
35        mid.next = None
36        left = head
37        
38        # 递归排序
39        left = self.sortList(left)
40        right = self.sortList(right)
41        
42        # 合并排序后的子链表
43        return merge(left, right)

 1class LRUCache:
 2    def __init__(self, capacity: int):
 3        # 使用 OrderedDict 来维护键值对的顺序
 4        self.data = OrderedDict()
 5        # 初始化缓存的容量
 6        self.capacity = capacity
 7
 8    def get(self, key: int) -> int:
 9        # 如果键存在于缓存中
10        if key in self.data:
11            # 将该键值对移动到有序字典的末尾（表示最近使用）
12            self.data.move_to_end(key)
13            # 返回对应的值
14            return self.data[key]
15        # 如果键不存在于缓存中，返回 -1
16        return -1
17
18    def put(self, key: int, value: int) -> None:
19        # 如果键已经存在于缓存中
20        if key in self.data:
21            # 更新该键的值
22            self.data[key] = value
23        else:
24            # 如果缓存已满
25            if len(self.data) >= self.capacity:
26                # 移除最久未使用的键值对（有序字典的头部）
27                self.data.popitem(last=False)
28            # 插入新的键值对
29            self.data[key] = value
30        # 将该键值对移动到有序字典的末尾（表示最近使用）
31        self.data.move_to_end(key)

 1class Solution:
 2    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
 3        if not head:
 4            return None
 5
 6        # Step 1: 创建新节点并插入到原节点后面
 7        curr = head
 8        while curr:
 9            # 创建新节点，并将其值设为当前节点的值
10            new_node = Node(curr.val, curr.next, None)
11            # 将新节点插入到当前节点和下一个节点之间
12            curr.next = new_node
13            # 移动到下一个原节点
14            curr = new_node.next
15
16        # Step 2: 设置新节点的随机指针
17        curr = head
18        while curr:
19            # 如果当前节点有随机指针
20            if curr.random:
21                # 新节点的随机指针应该指向原节点随机指针对应的新节点
22                curr.next.random = curr.random.next
23            # 移动到下一个原节点
24            curr = curr.next.next
25
26        # Step 3: 分离两个链表
27        old_head = head
28        new_head = head.next
29        curr_old = old_head
30        curr_new = new_head
31
32        while curr_old:
33            # 恢复原链表的结构
34            curr_old.next = curr_old.next.next if curr_old.next else None
35            # 构建新链表的结构
36            curr_new.next = curr_new.next.next if curr_new.next else None
37            # 移动到下一个原节点
38            curr_old = curr_old.next
39            # 移动到新链表的下一个新节点
40            curr_new = curr_new.next
41
42        return new_head

 1class Solution:
 2    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
 3        result = []  # 初始化一个空列表来存储遍历结果
 4        self.inorder(root, result)  # 调用辅助递归函数进行中序遍历
 5        return result  # 返回遍历结果列表
 6    
 7    def inorder(self, root, result):
 8        if not root:  # 如果当前节点为空，直接返回
 9            return
10        self.inorder(root.left, result)  # 递归遍历左子树
11        result.append(root.val)  # 将当前节点的值加入结果列表
12        self.inorder(root.right, result)  # 递归遍历右子树
13        return result  # 返回结果列表（虽然这个返回值在主方法中没有用到）

 1class Solution:
 2    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
 3        stack, result = [], []  # 初始化栈和结果列表
 4        
 5        while root or stack:  # 当根节点不为空或栈不为空时循环
 6            while root:  # 遍历到当前子树的最左节点
 7                stack.append(root)  # 将当前节点入栈
 8                root = root.left  # 移动到左子节点
 9            
10            root = stack.pop()  # 弹出栈顶节点（最左节点）
11            result.append(root.val)  # 将弹出节点的值加入结果列表
12            root = root.right  # 移动到右子节点
13        
14        return result  # 返回结果列表

1class Solution:
2    def maxDepth(self, root: Optional[TreeNode]) -> int:
3        if not root:
4            return 0
5        return max(self.maxDepth(root.left)+1,self.maxDepth(root.right)+1)

 1class Solution:
 2    # 使用广度优先搜索 (BFS) 计算最大深度
 3    def maxDepth(self, root: Optional[TreeNode]) -> int:
 4        if not root:
 5            return 0  # 空树的深度为0
 6        
 7        maxDepth = 1  # 初始最大深度为1（至少有根节点）
 8        queue = deque()  # 创建一个队列来进行BFS遍历
 9        queue.append(root)  # 将根节点添加到队列中
10        
11        while len(queue):  # 当队列不为空时，继续遍历
12            length = len(queue)  # 获取当前层的节点数量
13            for i in range(length):
14                head = queue.popleft()  # 弹出当前层的第一个节点
15                if head.left is not None:  # 如果左子节点存在，加入队列
16                    queue.append(head.left)
17                if head.right is not None:  # 如果右子节点存在，加入队列
18                    queue.append(head.right)
19            if len(queue) == 0:  # 如果队列为空，说明已遍历完所有节点
20                break
21            maxDepth += 1  # 每处理完一层，最大深度加1
22        
23        return maxDepth  # 返回最终的最大深度

 1class Solution:
 2    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
 3        def exchange(root):
 4            if not root:
 5                return 
 6            root.left,root.right=root.right,root.left
 7            exchange(root.left)
 8            exchange(root.right)
 9        exchange(root)
10        return root

 1class Solution:
 2    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
 3        if not root:
 4            return root        
 5        # 初始化队列并将根节点入队
 6        queue = deque([root])
 7        # 当队列不为空时，进行广度优先遍历
 8        while queue:
 9            # 弹出队首元素
10            head = queue.popleft()
11            # 交换左右子节点
12            head.left, head.right = head.right, head.left
13            # 将非空的左右子节点分别入队
14            if head.left:
15                queue.append(head.left)
16            if head.right:
17                queue.append(head.right)
18        # 返回反转后的树的根节点
19        return root

 1class Solution:
 2    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
 3        maxDiameter = 0
 4        
 5        def depth(node: TreeNode) -> int:
 6            nonlocal maxDiameter
 7            if not node:
 8                return 0
 9            leftDepth = depth(node.left)
10            rightDepth = depth(node.right)
11            # 更新最大直径
12            maxDiameter = max(maxDiameter, leftDepth + rightDepth)
13            
14            # 返回该节点的深度
15            return max(leftDepth, rightDepth) + 1
16        
17        depth(root)
18        return maxDiameter

 1class Solution:
 2    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
 3        """
 4        将排序数组转换为高度平衡的二叉搜索树。
 5        
 6        :param nums: 排序数组
 7        :return: 二叉搜索树的根节点
 8        """
 9        def helper(left: int, right: int) -> Optional[TreeNode]:
10            """
11            辅助函数，递归地将子数组转换为BST。
12            
13            :param left: 子数组的左边界
14            :param right: 子数组的右边界
15            :return: 当前子数组对应的BST的根节点
16            """
17            if left > right:
18                return None  # 如果左边界大于右边界，返回None，表示当前子数组为空
19            
20            # 选择中间元素作为根节点
21            mid = (left + right) // 2
22            root = TreeNode(nums[mid])
23            
24            # 递归构建左子树和右子树
25            root.left = helper(left, mid - 1)
26            root.right = helper(mid + 1, right)
27            
28            return root
29        
30        # 从整个数组开始递归构建BST
31        return helper(0, len(nums) - 1)

 1class Solution:
 2    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
 3        if not root:
 4            return []  # 如果根节点为空，直接返回空列表
 5        
 6        result = []  # 用于存储最终的层序遍历结果
 7        queue = deque([root])  # 初始化队列，将根节点加入队列
 8        
 9        while queue:
10            level_size = len(queue)  # 记录当前层的节点数
11            current_level = []  # 用于存储当前层的节点值
12            
13            for _ in range(level_size):
14                node = queue.popleft()  # 从队列中取出一个节点
15                current_level.append(node.val)  # 将节点值加入当前层的列表
16                
17                if node.left:
18                    queue.append(node.left)  # 如果节点有左子节点，将左子节点加入队列
19                if node.right:
20                    queue.append(node.right)  # 如果节点有右子节点，将右子节点加入队列
21            
22            result.append(current_level)  # 将当前层的节点值列表加入结果列表
23        
24        return result  # 返回最终的层序遍历结果

 1class Solution:
 2	def isValidBST(root: TreeNode) -> bool:
 3	    def helper(node, min_val=float('-inf'), max_val=float('inf')):
 4	        # 如果当前节点为空，返回 True，因为空树是有效的BST
 5	        if not node:
 6	            return True
 7	        
 8	        # 检查当前节点的值是否在指定的范围内
 9	        if not (min_val < node.val < max_val):
10	            return False
11	        
12	        # 递归检查左子树
13	        # 左子树的所有节点值必须小于当前节点的值
14	        left_valid = helper(node.left, min_val, node.val)
15	        
16	        # 递归检查右子树
17	        # 右子树的所有节点值必须大于当前节点的值
18	        right_valid = helper(node.right, node.val, max_val)
19	        
20	        # 只有当左右子树都满足条件时，当前节点才是有效的BST
21	        return left_valid and right_valid
22	    
23	    # 初始调用，范围是负无穷到正无穷
24	    return helper(root)

 1class Solution:
 2    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
 3        stack = []
 4        current = root
 5        
 6        while current or stack:
 7            # 先遍历左子树，将所有左子节点压入栈中
 8            while current:
 9                stack.append(current)
10                current = current.left
11            
12            # 从栈中弹出一个节点，访问该节点
13            current = stack.pop()
14            k -= 1  # 每访问一个节点，k 减 1
15            
16            # 如果 k 为 0，说明当前节点是第 k 小的元素，直接返回
17            if k == 0:
18                return current.val
19            
20            # 继续遍历右子树
21            current = current.right

 1class Solution:
 2    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
 3        if not root:
 4            return []  # 如果根节点为空，返回空列表
 5        
 6        result = []  # 用于存储从右侧看到的节点值
 7        queue = deque([root])  # 初始化队列，将根节点加入队列
 8        
 9        while queue:
10            # 当前层的节点数
11            level_length = len(queue)
12            
13            for i in range(level_length):
14                # 从队列中取出一个节点
15                node = queue.popleft()
16                
17                # 如果是当前层的最后一个节点，将其值加入结果列表
18                if i == level_length - 1:
19                    result.append(node.val)
20                
21                # 将当前节点的子节点加入队列
22                if node.left:
23                    queue.append(node.left)
24                if node.right:
25                    queue.append(node.right)
26        
27        return result  # 返回从右侧看到的节点值

 1class Solution:
 2    def flatten(self, root: Optional[TreeNode]) -> None:
 3        if not root:
 4            return
 5        
 6        # 先递归展开左右子树
 7        self.flatten(root.left)
 8        self.flatten(root.right)
 9        
10        # 如果有左子树
11        if root.left:
12            # 保存当前的右子树
13            right_subtree = root.right
14            
15            # 将左子树移动到右子树的位置
16            root.right = root.left
17            root.left = None  # 清空左子树
18            
19            # 找到右子树的最右节点
20            current = root
21            while current.right:
22                current = current.right
23            
24            # 将保存的原右子树接到最右节点
25            current.right = right_subtree

 1class Solution:
 2    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
 3        # 如果输入的先序或中序遍历为空，则返回 None
 4        if not preorder or not inorder:
 5            return None
 6        
 7        # 先序遍历的第一个元素是根节点
 8        root_val = preorder[0]
 9        root = TreeNode(root_val)
10        
11        # 在中序遍历中找到根节点的位置
12        root_index = inorder.index(root_val)
13        
14        # 递归构建左子树
15        # 先序遍历中，根节点后的前 `root_index` 个元素是左子树的先序遍历
16        # 中序遍历中，根节点前的 `root_index` 个元素是左子树的中序遍历
17        root.left = self.buildTree(preorder[1:1 + root_index], inorder[:root_index])
18        
19        # 递归构建右子树
20        # 先序遍历中，从 `1 + root_index` 到末尾的元素是右子树的先序遍历
21        # 中序遍历中，从 `root_index + 1` 到末尾的元素是右子树的中序遍历
22        root.right = self.buildTree(preorder[1 + root_index:], inorder[root_index + 1:])
23        
24        # 返回构建的根节点
25        return root

 1class Solution:
 2    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
 3        def dfs(node, currSum):
 4            if not node:
 5                return 0
 6            
 7            # 更新当前路径和
 8            currSum += node.val
 9            
10            # 计算从某个祖先节点到当前节点的路径和是否等于 targetSum
11            # 即 (currSum - targetSum) 是否在 prefix_sum_count 中存在
12            count = prefix_sum_count.get(currSum - targetSum, 0)
13            
14            # 更新前缀和字典，记录当前路径和出现的次数
15            prefix_sum_count[currSum] = prefix_sum_count.get(currSum, 0) + 1
16            
17            # 递归遍历左子树和右子树
18            count += dfs(node.left, currSum)
19            count += dfs(node.right, currSum)
20            
21            # 回溯：移除当前节点对应的路径和，以便不影响其他分支的路径计数
22            prefix_sum_count[currSum] -= 1
23            
24            return count
25        
26        # 前缀和哈希表，记录每个路径和出现的次数
27        # 初始值为 {0: 1}，表示从根节点到当前节点的路径和为0的路径有一条（即空路径）
28        prefix_sum_count = {0: 1}
29        
30        return dfs(root, 0)

 1class Solution:
 2    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
 3        
 4        # 如果当前节点为空，说明已经到达叶子节点的底部，返回 None
 5        # 如果当前节点是 p 或 q，说明我们找到了其中一个节点，返回当前节点
 6        if not root or root == p or root == q:
 7            return root
 8        
 9        # 在左子树中递归查找 p 和 q，返回在左子树中的结果
10        left = self.lowestCommonAncestor(root.left, p, q)
11        
12        # 在右子树中递归查找 p 和 q，返回在右子树中的结果
13        right = self.lowestCommonAncestor(root.right, p, q)
14        
15        # 如果左子树和右子树都找到了 p 或 q，那么当前节点 root 就是最近公共祖先
16        # 因为 p 和 q 分别在当前节点的左右子树中
17        if left and right:
18            return root
19        
20        # 如果只有左子树找到结果（right 为 None），说明 p 和 q 都在左子树中
21        # 返回左子树的结果
22        # 如果只有右子树找到结果（left 为 None），说明 p 和 q 都在右子树中
23        # 返回右子树的结果
24        return left if left else right

 1class Solution:
 2    def numIslands(self, grid: List[List[str]]) -> int:
 3        # 如果网格为空，直接返回0
 4        if not grid:
 5            return 0
 6
 7        # 获取网格的行数和列数
 8        rows, cols = len(grid), len(grid[0])
 9        count = 0
10
11        def dfs(r: int, c: int):
12            """
13            使用深度优先搜索 (DFS) 标记从 (r, c) 开始的所有相连的陆地。
14            """
15            # 检查边界条件，如果超出边界或者当前单元格是水，则返回
16            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
17                return
18            
19            # 将当前单元格标记为已访问（即变为 '0'）
20            grid[r][c] = '0'
21            
22            # 递归访问上下左右四个方向
23            dfs(r + 1, c)  # 下
24            dfs(r - 1, c)  # 上
25            dfs(r, c + 1)  # 右
26            dfs(r, c - 1)  # 左
27
28        # 遍历整个网格
29        for r in range(rows):
30            for c in range(cols):
31                # 如果当前单元格是陆地（'1'），则发现了一个新的岛屿
32                if grid[r][c] == '1':
33                    count += 1
34                    # 使用DFS标记整个岛屿
35                    dfs(r, c)
36
37        return count

 1class Solution:
 2    def orangesRotting(self, grid: List[List[int]]) -> int:
 3        if not grid:
 4            return -1
 5
 6        rows, cols = len(grid), len(grid[0])
 7        fresh_count = 0
 8        queue = deque()
 9
10        # 初始化队列和新鲜橘子计数
11        for r in range(rows):
12            for c in range(cols):
13                if grid[r][c] == 2:
14                    queue.append((r, c))  # 将所有初始腐烂的橘子加入队列
15                elif grid[r][c] == 1:
16                    fresh_count += 1  # 统计新鲜橘子的数量
17
18        # 定义四个方向：上下左右
19        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
20        minutes_passed = 0  # 记录时间
21
22        # 广度优先搜索
23        while queue and fresh_count > 0:
24            minutes_passed += 1  # 每处理完一轮，时间增加1分钟
25            for _ in range(len(queue)):
26                r, c = queue.popleft()  # 从队列中取出一个腐烂的橘子
27                for dr, dc in directions:
28                    nr, nc = r + dr, c + dc  # 计算相邻的单元格位置
29                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
30                        # 如果相邻单元格是新鲜橘子，将其变为腐烂橘子
31                        grid[nr][nc] = 2
32                        fresh_count -= 1  # 新鲜橘子数量减少1
33                        queue.append((nr, nc))  # 将新腐烂的橘子加入队列
34
35        # 检查是否还有新鲜橘子
36        if fresh_count == 0:
37            return minutes_passed  # 如果没有新鲜橘子，返回经过的分钟数
38        else:
39            return -1  # 如果还有新鲜橘子，返回-1

 1class Solution:
 2    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
 3        # 1. 初始化邻接表和入度表
 4        # 邻接表（graph）：记录每门课的后续课，即哪些课依赖于这门课
 5        # 入度表（in_degree）：记录每门课有多少门前置课（依赖的课程）
 6        graph = {i: [] for i in range(numCourses)}  # 每门课的后续课程列表
 7        in_degree = {i: 0 for i in range(numCourses)}  # 每门课的前置课个数
 8
 9        # 2. 构建图结构和入度表
10        # 遍历所有的前置课程关系 [a, b]，表示要先学课程 b 再学课程 a
11        for course, prereq in prerequisites:
12            graph[prereq].append(course)  # 课程 b 指向课程 a，表示 a 依赖 b
13            in_degree[course] += 1  # 课程 a 的前置课程数加 1
14
15        # 3. 找到所有没有前置课程的课程（即入度为 0 的课程）
16        queue = deque([course for course in in_degree if in_degree[course] == 0])
17
18        # 记录已经学完的课程数量
19        completed_courses = 0
20
21        # 4. 进行广度优先搜索（BFS）
22        while queue:
23            current_course = queue.popleft()  # 从队列中取出一门可以学习的课程
24            completed_courses += 1  # 这门课算作已经学完
25
26            # 对这门课的后续课程进行处理
27            for next_course in graph[current_course]:
28                in_degree[next_course] -= 1  # 该后续课的前置课程少了一门
29                if in_degree[next_course] == 0:  # 如果该课的前置课程已经全部学完
30                    queue.append(next_course)  # 将其加入队列
31
32        # 5. 判断是否所有课程都学完了
33        return completed_courses == numCourses  # 如果已学完的课程数量等于总课程数，则返回 True

 1class Trie:
 2    def __init__(self):
 3        # 初始化一个空的字典树根节点，根节点本身也是一个字典
 4        self.root = {}
 5
 6    def insert(self, word: str) -> None:
 7        # 从根节点开始逐个插入字符
 8        node = self.root
 9        for char in word:
10            # 如果当前字符不在当前节点中，添加这个字符
11            if char not in node:
12                node[char] = {}
13            node = node[char]
14        # 插入完成后，在末尾标记此位置为单词结束
15        node['#'] = True  # '#' 是结束标记符，表示这个路径为一个完整单词
16
17    def search(self, word: str) -> bool:
18        # 从根节点开始搜索字符
19        node = self.root
20        for char in word:
21            # 如果字符不在节点中，则表示字典树中不存在该单词
22            if char not in node:
23                return False
24            node = node[char]
25        # 判断最后的节点是否有单词结束标记
26        return '#' in node
27
28    def startsWith(self, prefix: str) -> bool:
29        # 从根节点开始逐个字符检查前缀
30        node = self.root
31        for char in prefix:
32            # 如果前缀中的字符不在字典树中，返回 False
33            if char not in node:
34                return False
35            node = node[char]
36        # 如果可以走完前缀，说明存在该前缀
37        return True