leetcode刷题记录

这个文档仅用于记录leetcode热题100的记录，重点记录我这个菜鸡认为惊为天人的解题思路。

有关python的collections库

deque

deque（双端队列）是一个线程安全的双向队列，支持在两端快速添加和删除元素。

from collections import deque

# 创建一个deque
d = deque([1, 2, 3])

# 在右侧添加元素
d.append(4)
print(d)  # 输出: deque([1, 2, 3, 4])

# 在左侧添加元素
d.appendleft(0)
print(d)  # 输出: deque([0, 1, 2, 3, 4])

# 从右侧移除元素
d.pop()
print(d)  # 输出: deque([0, 1, 2, 3])

# 从左侧移除元素
d.popleft()
print(d)  # 输出: deque([1, 2, 3])

Counter

Counter是一个字典的子类，用于计数可哈希对象

from collections import Counter

# 创建一个Counter
c = Counter(['apple', 'orange', 'apple', 'pear', 'orange', 'banana'])

# 查看计数
print(c)  # 输出: Counter({'apple': 2, 'orange': 2, 'pear': 1, 'banana': 1})

# 获取某个元素的计数
print(c['apple'])  # 输出: 2

# 更新计数
c.update(['apple', 'orange'])
print(c)  # 输出: Counter({'apple': 3, 'orange': 3, 'pear': 1, 'banana': 1})

defaultdict

defaultdict是dict的一个子类，提供了一个默认值，当访问不存在的键时不会抛出KeyError

from collections import defaultdict

# 创建一个defaultdict
dd = defaultdict(int)

# 访问不存在的键
print(dd['a'])  # 输出: 0

# 更新值
dd['b'] += 1
print(dd)  # 输出: defaultdict(<class 'int'>, {'a': 0, 'b': 1})

哈希

【哈希】两数之和

题面

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

solution：暴力题解

class Solution:

    def twoSum(self, nums: List[int], target: int) -> List[int]:

        res=[]

        for i in range(len(nums)):

            for j in range(i+1,len(nums)):

                if (nums[i]+nums[j]==target):

                    res.append(i)

                    res.append(j)

        return res

【哈希】异位字符

题面

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

Solution：defultdict

将排序后的字符当作键，遍历所有字符串，符合要求的存为值。

class Solution:

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:

        anagramdict=defaultdict(list)

        for s in strs:

            key="".join(sorted(s))

            anagramdict[key].append(s)

        return list(anagramdict.values())

【哈希】最长连续序列

题面

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

Solution 遍历

def longestConsecutive(self, nums: List[int]) -> int:

        num_set = set(nums)  # 去重并存入集合

        max_length = 0

        for num in num_set:

            # 检查是否是连续序列的起点

            if num - 1 not in num_set:

                current_num = num

                current_length = 1

                # 向后扩展序列

                while current_num + 1 in num_set:

                    current_num += 1

                    current_length += 1

                # 更新最长长度

                max_length = max(max_length, current_length)

        return max_length

动态规划

【动态规划】爬楼梯

题面

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

Solution

动态规划自底向上

class Solution:

    def climbStairs(self, n: int) -> int:

        if n==1:

            return 1

        dp=[0]*(n+1)

        dp[0]=0

        dp[1]=1

        dp[2]=2

        for i in range(3,n+1):

            dp[i]=dp[i-1]+dp[i-2]

        return dp[n]

【动态规划】杨辉三角

题面

 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

Solution

class Solution:

    def generate(self, numRows: int) -> List[List[int]]:

        triangle=[]

        for i in range(numRows):

            num_row=[1]*(i+1)

            for j in range(1,i):

                num_row[j]=triangle[i-1][j-1]+triangle[i-1][j]

            triangle.append(num_row)

        return triangle

双指针

【双指针】移动0

题面

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。

Solution：

双指针，i用来遍历所有元素，j寻找放置非0的位置，然后再一次循环把剩下的位置置为0

class Solution:

    def moveZeroes(self, nums: List[int]) -> None:

        """

        Do not return anything, modify nums in-place instead.

        """

        j=0

        for i in range(len(nums)):

            if nums[i]!=0:

                nums[j]=nums[i]

                j+=1

        for i in range(j,len(nums)):

            nums[i]=0

        return nums

【双指针】乘最多水的容器

题面

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

Solution

设置双指针，左右各一。

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        j=0
        for i in range(len(nums)):
            if nums[i]!=0:
                nums[j]=nums[i]
                j+=1

        for i in range(j,len(nums)):
            nums[i]=0
        return nums

【双指针】三数之和

题面：

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

Solution：

双指针之前排序，固定第一个数nums[i]为结果中的第一个数（这个数的结果等于另外两个数求和取负），然后在剩下的元素中设置双指针挨个寻找符合要求的数，相同则跳过。

class Solution:

    def threeSum(self, nums: List[int]) -> List[List[int]]:

        res=[]

        nums.sort()

        for i in range(len(nums)-2):

            if i>0 and nums[i]==nums[i-1]:

                continue

            target=-nums[i]

            left=i+1

            right=len(nums)-1

            while left<right:

                current_sum=nums[left]+nums[right]

                if current_sum==target:

                    res.append([nums[i],nums[left],nums[right]])

                    left+=1

                    right-=1

                    while left<right and nums[left]==nums[left-1]:

                        left+=1

                    while left<right and nums[right+1]==nums[right]:

                        right-=1

                elif current_sum < target:

                    left += 1

                else:

                    right -= 1

        return res

【双指针】接雨水

题面

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水

Solution:

双指针分别从左右两边开始遍历，谁小处理谁。如果左边小，比较左边当前位置的高度和最高位置谁大，要是当前位置大于最大位置，则更新最大位置，否则计算雨水（最高-当前），然后左边指针右移；右边同理。

class Solution:
   def trap(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        left_max, right_max = height[left], height[right]
        water = 0

        while left < right:
            if height[left] < height[right]:
                left += 1
                left_max = max(left_max, height[left])
                water += left_max - height[left]
            else:
                right -= 1
                right_max = max(right_max, height[right])
                water += right_max - height[right]
        return water       return water

滑动窗口

【滑动窗口】无重复字符的最长字串

题面：

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

Solution：

1. 初始化：seen 集合存储当前窗口字符，left 指针初始化为 0，max_length 记录最长子串长度。

2. 遍历字符串：

   • 字符存在时：移动 left 并从 seen 中移除字符，直到 s[right] 不在集合中。

   • 字符不存在时：添加到 seen，并更新 max_length。

3. 返回结果：max_length 即为最长无重复字符子串的长度。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        seen = set()
        left = 0
        max_length = 0

        for right in range(len(s)):
            while s[right] in seen:
                seen.remove(s[left])
                left += 1
            seen.add(s[right])
            max_length = max(max_length, right - left + 1)

        return max_length

【滑动窗口】找到字符串中所有字母异位词

题面

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

Solution

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(s) < len(p):
            return []

        p_len = len(p)
        p_sorted = sorted(p)
        res = []

        for i in range(len(s) - p_len + 1):
            window = s[i:i+p_len]
            if sorted(window) == p_sorted:
                res.append(i)

        return res

数组

【普通数组】最大子数和

题目

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

Solution

Kadane算法（动态规划）

1. 初始化：

   • max_current：记录以当前元素结尾的最大子数组和。

   • max_global：记录全局最大子数组和。

2. 遍历数组：

   • 对于每个元素，更新 max_current：

     • 要么将当前元素加入之前的子数组（max_current + nums[i]），

     • 要么以当前元素作为新的子数组起点（nums[i]）。

   • 更新 max_global 为 max_current 和 max_global 中的较大值。

3. 返回结果：max_global 即为最大子数组和。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_current=globalmax_current=nums[0]
        for num in nums[1:]:
            max_current=max(num,max_current+num)
            globalmax_current=max(globalmax_current,max_current)
        return globalmax_current

【普通数组】合并区间

题目

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

Solution

1. 排序区间：首先按照区间的起始点进行排序，这样相邻的区间更容易判断是否重叠。

2. 合并区间：遍历排序后的区间列表，逐个检查当前区间是否与结果列表中的最后一个区间重叠：

   • 如果重叠，则合并这两个区间（更新结果列表最后一个区间的结束点为两者中的较大值）。

   • 如果不重叠，则将当前区间直接加入结果列表。

class Solution:

    def merge(self, intervals: List[List[int]]) -> List[List[int]]:

        if not intervals:

            return []

        intervals.sort(key=lambda x: x[0])

        res=[intervals[0]]

        for current in intervals[1:]:

            last=res[-1]

            if last[1] >= current[0]:

                last[1]=max(last[1],current[1])

            else:

                res.append(current)

        return res

【普通数组】轮转数组

题目

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

Solution

class Solution:#python切片
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k %= n
        nums[:] = nums[-k:] + nums[:-k]

1. 创建一个新数组，将原数组的元素按照轮转后的位置放入新数组。

2. 计算每个元素的新位置：(i + k) % n，其中 n 是数组长度。

   class Solution:
       def rotate(self, nums: List[int], k: int) -> None:
           n = len(nums)
           rotated = [0] * n
           for i in range(n):
               rotated[(i + k) % n] = nums[i]
           nums[:] = rotated

【普通数组】除自身以外的数组乘积

题目

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

Solution

维护两个数组，对于numi，lefti和righti分别表示左右两边的乘积

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n=len(nums)
        right=[1]*n
        left=[1]*n
        res=[1]*n

        for i in range(1,n):
            left[i]=left[i-1]*nums[i-1]
        for i in range(n-2,-1,-1):
            right[i]=right[i+1]*nums[i+1]

        for i in range(0,n):
            res[i]=left[i]*right[i]

        return res

【普通数组】最小数

题目

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

Solution

来自ds的解法

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)

        # 检查是否包含1
        if 1 not in nums:
            return 1

        # 预处理：将所有非正数和大于n的数替换为1
        for i in range(n):
            if nums[i] <= 0 or nums[i] > n:
                nums[i] = 1

        # 使用索引作为哈希键，标记出现的数字
        for i in range(n):
            num = abs(nums[i])
            if num == n:
                nums[0] = -abs(nums[0])  # 用索引0表示n
            else:
                nums[num] = -abs(nums[num])

        # 查找第一个正数的索引
        for i in range(1, n):
            if nums[i] > 0:
                return i

        # 检查n是否出现
        if nums[0] > 0:
            return n

        # 如果1到n都出现，则返回n+1
        return n + 1

矩阵

【矩阵】矩阵置零

题面

给定一个 *m* x *n* 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法

Solution：

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        marks=[]
        len_col=len(matrix)
        len_row=len(matrix[0])
        for col in range(len_col):
            for row in range(len_row):
                if matrix[col][row]==0:
                    marks.append([col,row])

        for mark in marks:
            for col in range(len_col):
                matrix[col][mark[1]]=0
            for row in range(len_row):
                matrix[mark[0]][row]=0

【矩阵】螺旋矩阵

题面：

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

Solution:

【边界模拟】

1. 初始化边界：

   • 上边界 top = 0，下边界 bottom = m - 1

   • 左边界 left = 0，右边界 right = n - 1

2. 循环遍历：

   • 从左到右遍历上边界，完成后上边界下移（top += 1）

   • 从上到下遍历右边界，完成后右边界左移（right -= 1）

   • 检查是否仍需遍历（top <= bottom 且 left <= right）：

     • 从右到左遍历下边界，完成后下边界上移（bottom -= 1）

     • 从下到上遍历左边界，完成后左边界右移（left += 1）

3. 终止条件：当所有边界相遇或交叉时停止。

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        left=0
        top=0
        right=len(matrix[0])-1
        bottom=len(matrix)-1
        res=[]
        while left<=right and top<=bottom:
            for i in range(left,right+1):
                res.append(matrix[top][i])
            top+=1
            for j in range(top,bottom+1):
                res.append(matrix[j][right])
            right-=1

            if left<=right and top<=bottom:
                for i in range(right,left-1,-1):
                    res.append(matrix[bottom][i])

                bottom-=1
                for j in range(bottom,top-1,-1):
                    res.append(matrix[j][left])

                left+=1

        return res

【矩阵】旋转图像

题面

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

Solution

1. 转置矩阵：首先将矩阵的行和列互换，即转置矩阵。转置后的矩阵会将原来的行变为列，原来的列变为行。

2. 翻转每一行：然后将转置后的矩阵的每一行进行翻转，即第一个元素和最后一个元素交换，第二个元素和倒数第二个元素交换，以此类推。

这样操作后，矩阵就会顺时针旋转 90 度。

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n=len(matrix)
        for i in range(n):
            for j in range(i,n):
                matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]
        
        for i in range(n):
            matrix[i].reverse()

【矩阵】搜索二维矩阵Ⅱ

题面

编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

Solution

从矩阵的左下角或者右上角开始遍历，因为这两个位置分别对应所在行的最大（小）值和所在列的最小（大）值。示例从右上角开始，如果当前值大于目标，则行号+1，小于目标则列号减一。

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix:
            return False
        n=len(matrix)
        m=len(matrix[0])

        row=0
        col=m-1
        while row<n and col>=0:
            if matrix[row][col]==target:
                return True
            elif matrix[row][col]<target:
                row+=1
            else:
                col-=1
        return False

【矩阵】和为K的子数组

题面

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

Solution：

一开始用滑动窗口结果超时了，换个思路，前缀和+哈希表：

1. 前缀和：定义 prefix_sum[i] 为 nums[0] + nums[1] + ... + nums[i-1]。

2. 关键观察：子数组 nums[i..j] 的和可以表示为 prefix_sum[j+1] - prefix_sum[i]。

3. 哈希表优化：

   • 用哈希表记录前缀和出现的次数。

   • 对于当前前缀和 curr_sum，检查 curr_sum - k 是否在哈希表中，若存在则累加计数。

from collections import defaultdict

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        prefix_count = defaultdict(int)
        prefix_count[0] = 1  # 初始前缀和为0出现1次
        curr_sum = 0
        count = 0
        
        for num in nums:
            curr_sum += num
            # 检查是否存在前缀和满足 curr_sum - prefix = k
            if (curr_sum - k) in prefix_count:
                count += prefix_count[curr_sum - k]
            # 记录当前前缀和
            prefix_count[curr_sum] += 1
        
        return count

链表

【链表】反转链表

题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

Solution

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        curr = head

        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node

        return prev

【链表】交叉链表

题目

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

Solution

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        if not headA or not headB:
            return None
        hA, hB = headA, headB
        while hA is not hB:
            hA = hA.next if hA else headB
            hB = hB.next if hB else headA
        return hA

思路

设两个指针 pA 和 pB，分别从 headA 和 headB 出发。

每次向前走一步，如果到达链表末尾，则切换到另一个链表的头。

如果两个链表相交，最终会在相交点相遇；

如果不相交，则会同时走到 None，返回 None。

为什么有效？

指针 A 走过的路径：lenA + lenB

指针 B 走过的路径：lenB + lenA

若相交，则在交点对齐；若不相交，则同时为 None。

【链表】回文链表

题目

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
输入：head = [1,2,2,1]
输出：true
输入：head = [1,2]
输出：false

Solution

1. 使用两个指针（快慢指针）寻找链表中点，慢指针一次走一格，快指针一次走两格，这样快指针走完时，慢指针就指向中点。
2. 反转从慢指针到快指针之间的链表。
3. 对比反转后的链表和整个链表的前半部分是否相同。

   # Definition for singly-linked list.
   # class ListNode:
   #     def __init__(self, val=0, next=None):
   #         self.val = val
   #         self.next = next
   
   from typing import Optional
   
   class Solution:
       def isPalindrome(self, head: Optional[ListNode]) -> bool:
           if not head or not head.next:
               return True
   
           # 1. 快慢指针找中点
           slow, fast = head, head
           while fast and fast.next:
               slow = slow.next
               fast = fast.next.next
   
           # 2. 反转后半部分
           prev = None
           curr = slow
           while curr:
               nxt = curr.next
               curr.next = prev
               prev = curr
               curr = nxt
   
           # 3. 对比两半部分
           p1, p2 = head, prev
           while p2:  # 后半部分长度 <= 前半部分
               if p1.val != p2.val:
                   return False
               p1 = p1.next
               p2 = p2.next
   
           return True

【链表】环形链表

题面

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

Solution

设置两个指针：

slow 每次走一步

fast 每次走两步

如果链表里有环：

fast 和 slow 一定会在环里相遇（类似跑道上快慢选手总能相遇）。

如果链表无环：

fast 或 fast.next 会先到达 None，说明走到链表末尾。

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head:
            return False

        slow ,fast = head, head.next
        while slow != fast:
            if not fast or not fast.next:
                return False
            slow = slow.next
            fast = fast.next.next
        return True

【链表】环形链表Ⅱ

题面

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

Solution

先寻找之前题目中slow和fast相遇的位置，然后将slow移到开始，再让两个指针同速往前遍历，再次相遇时就是环的入口。

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return None
        fast, slow = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow==fast:
                break
          
        else:
            return None
        slow = head
        while slow!=fast:
            slow = slow.next
            fast = fast.next
        return slow 

【链表】合并两个有序链表

题面

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

Solution

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1 and not list2:
            return list1
        if list2 and not list1:
            return list2
        if not list1 and not list2:
            return None
        
        dummy = ListNode()
        current = dummy

        while list1 and list2:
            if list1.val < list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next
            current = current.next
        if list1:
            current.next=list1
        elif list2:
            current.next = list2

        return dummy.next

二叉树

【二叉树】中序遍历

题面

中序遍历二叉树

Solution

递归

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        result=[]
        def dfs(node):
            if not node:
                return []
            dfs(node.left)
            result.append(node.val)
            dfs(node.right)
        dfs(root)
        return result

迭代

def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        stack = []
        current = root
        
        while current or stack:
            # 遍历左子树，将所有左节点压入栈中
            while current:
                stack.append(current)
                current = current.left
            
            # 弹出栈顶节点，访问该节点
            current = stack.pop()
            result.append(current.val)
            
            # 移动到右子树
            current = current.right
        
        return result

【二叉树】最大深度

题面

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

Solution

递归

递归寻找最大深度

# 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
        max_left = self.maxDepth(root.left)
        max_right = self.maxDepth(root.right)
        return max(max_left,max_right)+1

迭代

借助队列，首先将根节点入队。当队列非空时，进行以下步骤：

• 队尾元素弹出，记录该层节点数量，弹出队尾；
• 循环所有该层节点，判断是否有左右子树
• 若有子树，将该节点入队，深度+1

  class Solution:
      def maxDepth(self, root: Optional[TreeNode]) -> int:
          if not root:
              return 0
          
          queue = deque([root])
          depth = 0
          
          while queue:
              level_size = len(queue)
              for _ in range(level_size):
                  node = queue.popleft()
                  if node.left:
                      queue.append(node.left)
                  if node.right:
                      queue.append(node.right)
              depth += 1
          
          return depth

【二叉树】翻转

题面

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

Solution

递归

# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        root.right, root.left = root.left, root.right

        self.invertTree(root.left)
        self.invertTree(root.right)

        return root

迭代

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        
        queue = deque([root])
        
        while queue:
            node = queue.popleft()
            
            # 交换当前节点的左子树和右子树
            node.left, node.right = node.right, node.left
            
            # 将左子节点加入队列（如果存在）
            if node.left:
                queue.append(node.left)
            
            # 将右子节点加入队列（如果存在）
            if node.right:
                queue.append(node.right)
        
        return root