Hot100刷题记录

二叉树

二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def dfs(node: Optional[TreeNode]) -> None:
            if node is None:
                return
            dfs(node.left)       # 左
            ans.append(node.val) # 根（这行代码移到前面就是前序，移到后面就是后序）
            dfs(node.right)      # 右

        ans = []
        dfs(root)
        return ans

掌握访问元素的时机即可。

二叉树的最大深度

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

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

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode]) -> int:
            if node is None:
                return 0
            # 当前深度 = 1 + 左右子树中较大的那个深度
            return 1 + max(dfs(node.left), dfs(node.right))

        return dfs(root)

这两个问题都非常敏锐，触及了 Python 作用域和编码风格的核心细节。我们逐一拆解。

---

问题 1：为什么我之前用 is None，之前又说推荐 not node？

抱歉造成了混淆！ 这确实是我在示例代码中的风格不一致。

• 实际情况： 在 LeetCode 二叉树题目中，if not node: 和 if node is None: 功能完全等价。
• 为什么我之前用了 is None： 这是一种“防御性编程”的习惯。在工程代码中，is None 更严谨（防止对象重载了 __bool__ 导致误判）。但在算法题里，TreeNode 不会重载布尔值，所以 if not node: 完全没问题。
• 结论： 在刷算法题时，请坚持使用 if not node:。它更短、更通用，也是社区主流写法。我之前的示例用了 is None 只是个人习惯，你可以直接改回 if not node:。

---

问题 2：为什么 inorderTraversal 修改 result 没事，maxDepth 修改 result 就报错？

这是 Python 中最容易让人困惑的作用域（Scope）规则。核心区别在于：你是“修改了对象的内容”，还是“重新赋值了变量名”。

1. inorderTraversal 的情况（成功）

def inorderTraversal(self, root):
    result = []  # result 指向一个列表对象（可变对象）

    def dfs(node):
        # 注意这里：我们没有写 result = ...
        result.append(node.val)  # 我们是在调用列表对象的方法
        # ...

• 关键点： result.append(...) 不是赋值操作。
• 发生了什么：
  1. Python 在 dfs 内部查找变量名 result。
  2. 因为它没有看到 result = ... 这样的赋值语句，Python 认为 result 不是局部变量。
  3. 于是它去外层函数（闭包）里找，找到了 result = [] 那个列表。
  4. 然后在这个列表对象上执行 .append() 方法。
  5. 列表的内容变了，但 result 这个变量名指向的内存地址没变。
• 结论： 只要不对变量名进行 = 赋值，就可以直接读取和使用外层变量。

2. maxDepth 的情况（报错）

def maxDepth(self, root):
    result = 0  # result 指向一个整数对象（不可变对象）

    def dfs(node, depth):
        # 注意这里：出现了赋值操作！
        if depth > result:
            result = depth  # 👈 这一行决定了 result 是局部变量
        # ...

• 关键点： result = depth 是 赋值操作。
• 发生了什么：
  1. Python 在编译 dfs 函数时，发现代码里有 result = ...。
  2. Python 立即决定：result 是 dfs 函数的局部变量。
  3. 当代码运行到 if depth > result: 时，它试图读取局部变量 result。
  4. 但是，局部变量 result 此时还没有被赋值（赋值语句在 if 内部，且还没执行到）。
  5. 报错： UnboundLocalError（局部变量在赋值前被引用）。
• 结论： 一旦你在函数内部对变量名使用了 =，Python 就把它当成局部变量，从而“屏蔽”了外层的同名变量。

---

直观类比：盒子与标签

想象 result 是一个标签，贴在某个盒子上。

• inorderTraversal (列表):

  • 外层贴了个标签 result 指向一个箱子。
  • 内层函数说：“找到 result 标签指向的箱子，往里面放个苹果 (append)。”
  • 结果： 箱子里的东西变了，标签没动。✅ 成功。

• maxDepth (整数):

  • 外层贴了个标签 result 指向数字 0。
  • 内层函数说：“我要把 result 这个标签撕下来，贴到数字 depth 上 (result = depth)。”
  • Python 编译器说：“等等，既然你要在内层重新贴标签，那内层就有自己的 result 标签了。但在你重新贴之前，我想读一下内层的 result 指向哪，发现还没贴呢！”
  • 结果： 报错。❌ 失败。

总结与修正建议

操作类型	代码示例	是否触发局部作用域	是否需要 nonlocal
修改可变对象内容	result.append(), result.extend()	否 (读取外层变量)	不需要
重新赋值变量名	result = 1, result += 1, result = depth	是 (创建局部变量)	需要 (nonlocal result)

对于你的 maxDepth 代码，有两种改法：

1. 加 nonlocal (最小改动):

   def dfs(node, depth):
       nonlocal result  # 告诉 Python 别把 result 当局部变量
       if node is None:
           return
       # ...
       if depth > result:
           result = depth
   

2. 改用返回值 (最佳实践): 不要依赖外部变量，直接让递归返回深度（如我上一个回答的方法三）。这避免了作用域问题，代码也更干净。

希望这个解释能帮你彻底搞懂 Python 的闭包和作用域机制！

翻转二叉树

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

# 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
        root.left, root.right = root.right, root.left

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

二叉树的直径

给定一个二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

# 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:
        result = 0
        def dfs(node: Optional[TreeNode]) -> int:
            nonlocal result
            if node is None:
                return 0
            left = dfs(node.left)
            right = dfs(node.right)
            result = max(left + right, result)
            return 1 + max(left, right)

        dfs(root)
        return result

我的思路其实也很简单，借由之前的深度计算方法，计算得到经过以每个节点为根的直径的最大值，与全局进行比较，最终得出结果。

对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

# 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:
        # 如果根节点为空，视为对称
        if not root:
            return True

        # 定义辅助函数：判断两棵树是否互为镜像
        def is_mirror(left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:
            # 1. 如果两个节点都为空，则对称
            if not left and not right:
                return True

            # 2. 如果其中一个为空（另一个不为空），则不对称
            # 注意：上面已经排除了都为空的情况，所以这里只要有一个为空就是 False
            if not left or not right:
                return False

            # 3. 如果两个节点都不为空，但值不相等，则不对称
            if left.val != right.val:
                return False

            # 4. 递归检查：
            # 左子树的左边  <->  右子树的右边
            # 左子树的右边  <->  右子树的左边
            return is_mirror(left.left, right.right) and is_mirror(left.right, right.left)

        # 从根节点的左右子树开始检查
        return is_mirror(root.left, root.right)

也就是对称着进行访问遍历，但是需要保证是在依次遍历中同时遍历两边，因此要写在一个方法调用中。

二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        result = []
        queue = deque()
        queue.append(root)
        row = []
        sign = root
        while queue:
            node = queue.popleft()
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
            row.append(node.val)
            if node == sign:
                result.append(row)
                row = []
                if queue:
                    sign = queue[-1]

        return result

层序遍历的思路是，从根节点开始，将根节点加入队列。然后，从队列中取出一个节点，将其加入结果列表。如果该节点有左子节点，则将其加入队列。如果该节点有右子节点，则将其加入队列。重复这个过程，直到队列为空。

上面是我自己的写法，写的有点丑陋，核心难点在于如何确定当前层已经遍历完，下一层开始。我是想到了用一个变量记录当前层最右边的节点，当遍历到该节点时，说明当前层已经遍历完，下一层开始。

两种题解：都是直接利用嵌套循环的思路，每一个内层循环就是每一层。

方法一：两个数组

每一次数组存储的就是这一行的节点，挨个遍历即可，用另一个数组记录下一层的节点，当遍历完当前层的节点时，将下一层的节点赋给当前层的节点，继续遍历。确实也就模拟出了队列的思路。

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        ans = []
        cur = [root]
        while cur:
            nxt = []
            vals = []
            for node in cur:
                vals.append(node.val)
                if node.left:  nxt.append(node.left)
                if node.right: nxt.append(node.right)
            cur = nxt
            ans.append(vals)
        return ans

方法二：一个队列

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        ans = []
        q = deque([root])
        while q:
            vals = []
            for _ in range(len(q)):
                node = q.popleft()
                vals.append(node.val)
                if node.left:  q.append(node.left)
                if node.right: q.append(node.right)
            ans.append(vals)
        return ans

二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

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

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None
        left_tail = self.flatten(root.left)
        right_tail = self.flatten(root.right)
        if left_tail:
            left_tail.right = root.right  # 左子树链表 -> 右子树链表
            root.right = root.left  # 当前节点 -> 左右子树合并后的链表
            root.left = None
        return right_tail or left_tail or root

我们需要的是先将左子树展开为链表，然后将右子树展开为链表。然后，将左子树链表挂载到当前节点的右子树，将当前节点的左子树置为 None。此时如何将右子树链表挂载到左子树链表末尾呢？因此我们的 DFS需要返回链表的尾节点。

链表合并完成后，返回合并后的链表的尾节点，也就是右子树链表的尾节点。如果右子树是空的，则返回左子树链表的尾节点。如果左右子树都是空的，返回当前节点。

总结“何时该在叶节点 return"的原则。

---

1. 核心逻辑解析：为什么要返回尾节点？

扁平化二叉树的核心难点在于：当把左子树移到右边后，如何把原来的右子树接在左子树的后面？

    1
   / \
  2   5
 / \   \
3   4   6

1. 递归处理左子树（2-3-4），我们需要知道左子树拉直后的 最后一个节点（尾节点） 是谁（这里是 4）。
2. 递归处理右子树（5-6），我们需要知道右子树拉直后的 尾节点 是谁（这里是 6）。
3. 连接操作：
   • 把 1 的右指针指向 2（左子树头）。
   • 把 4（左子树尾）的右指针指向 5（右子树头）。
   • 把 1 的左指针置空。
4. 返回值：当前这整棵树（1-2-3-4-5-6）拉直后的 尾节点（6） 需要返回给上一层（如果 1 是某个节点的左孩子，上一层需要把 1 的尾连起来）。

结论： 这两个函数虽然名叫 flatten，但实际上它们充当了 dfs helper 的角色，返回值是当前子树扁平化后的尾节点。

---

2. 两段代码的对比分析

代码 1：统一处理（隐式叶节点）

# 终止条件只处理了 None
if root is None:
    return None

# ... 递归 ...

# 核心区别在这里 👇
# 通过逻辑或运算，自动判断谁是尾节点
return right_tail or left_tail or root

• 逻辑： 它不专门区分“叶节点”。
  • 如果有右子树，right_tail 存在，返回它（整棵树的尾在右边）。
  • 如果没有右子树但有左子树，right_tail 为 None，返回 left_tail（整棵树的尾在左边）。
  • 如果左右都没有（叶节点），前两个都为 None，返回 root（自己就是尾）。
• 优点： 代码更简洁，少了一个 if 判断，逻辑复用性高。
• 缺点： 哪怕到了叶节点，也要执行完后面的逻辑才返回，多了一层函数栈。

代码 2：显式处理叶节点（优化终止条件）

# 终止条件处理了 None 和 叶节点
if root is None:
    return
if (root.left is None) and (root.right is None):
    return root  # 👈 叶节点直接返回自己

# ... 递归 ...

# 因为排除了叶节点，这里必然至少有一个子树存在
return right or left

• 逻辑： 它在递归开始前就拦截了叶节点。
  • 既然是叶节点，扁平化后尾节点就是自己，直接 return root。
  • 既然能走到下面，说明 root 一定有孩子。那么 right 和 left 至少有一个不是 None。
  • 所以 return right or left 是安全的，不需要再 or root。
• 优点： 递归深度稍微浅一点（叶节点不再向下递归），逻辑意图更明确（叶节点不需要处理连接逻辑）。
• 缺点： 多了一个 if 判断，代码行数稍多。

---

3. 为什么都能行？（执行流追踪）

假设树是 1 -> 2 (1 是根，2 是左孩子)。

代码 1 的执行流：

1. flatten(1): 调用 flatten(2) (左), flatten(None) (右)。
2. flatten(2): 调用 flatten(None), flatten(None)。
   • 返回 None or None or 2 -> 返回 2。
3. 回到 flatten(1): left_tail = 2, right_tail = None。
   • 执行连接：2.right = None, 1.right = 2, 1.left = None。
   • 返回 None or 2 or 1 -> 返回 2。
4. 正确。

代码 2 的执行流：

1. flatten(1): 调用 flatten(2), flatten(None)。
2. flatten(2): 命中叶节点判断 (left/right 均为 None)。
   • 直接返回 2。 (不再向下递归)
3. 回到 flatten(1): left = 2, right = None。
   • 执行连接。
   • 返回 None or 2 -> 返回 2。
4. 正确。

---

4. 什么时候该在叶节点就 return？

这是一个关于 递归设计模式 的问题。请遵循以下原则：

情况 A：必须在叶节点 return（或处理 None 时） 如果函数后续的逻辑依赖于“节点有孩子”，你必须提前返回，否则会报错（如 NoneType has no attribute 'val'）。

def dfs(node):
    # ❌ 错误：如果 node 是叶节点，node.left 是 None，下一行会报错
    # if node.left.val > 10:
    #     ...

    # ✅ 正确：先确保有孩子
    if not node.left and not node.right:
        return
    if node.left.val > 10:
        ...

情况 B：可以在叶节点 return（优化） 如果后续逻辑对叶节点是安全的（比如你用了 if node.left: 保护），你可以选择：

1. 不 return（像代码 1）：让逻辑自然流淌到最后，通过返回值处理。适合逻辑简单、想少写 if 的情况。
2. return（像代码 2）：作为剪枝优化。适合递归很深、想减少函数调用开销的情况，或者为了简化最后的 return 逻辑（如代码 2 不需要 or root）。

情况 C：必须在叶节点 return（逻辑语义） 如果叶节点的含义与其他节点不同。 例如：计算路径和。叶节点代表路径结束，可能需要特殊处理（如将当前路径加入结果集），而中间节点只是累加。

---

5. 一个重要的潜在问题（LeetCode 签名）

虽然你的代码逻辑是通的，但在 LeetCode 原题 (114. Flatten Binary Tree to Linked List) 中，函数签名通常是：

def flatten(self, root: Optional[TreeNode]) -> None:

注意返回类型是 None。

• 你的代码中写了 -> Optional[TreeNode] 并且 return 了节点。
• 在 LeetCode 上，如果签名是 -> None，你 return 的值会被忽略。但你的递归调用 left_tail = self.flatten(root.left) 会接收到 None，导致逻辑崩溃。
• 正确做法： 如果题目强制 -> None，你需要定义一个内部辅助函数来返回尾节点。

标准工程写法（兼容 -> None 签名）：

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        def dfs(node: Optional[TreeNode]) -> Optional[TreeNode]:
            """返回扁平化后的尾节点"""
            if not node:
                return None
            if not node.left and not node.right:
                return node

            left_tail = dfs(node.left)
            right_tail = dfs(node.right)

            if left_tail:
                left_tail.right = node.right
                node.right = node.left
                node.left = None

            return right_tail or left_tail or node

        dfs(root)  # 外部调用辅助函数，主函数不返回任何东西

总结建议

1. 代码 1 和 代码 2 逻辑都对。代码 1 更简洁（Pythonic），代码 2 更明确（显式剪枝）。
2. 关于叶节点 return：
   • 如果为了简化返回值逻辑（避免写 or root），像代码 2 那样在叶节点 return 是很好的技巧。
   • 如果为了代码最短，像代码 1 那样统一处理更省事。
3. 注意题目签名：如果题目要求 -> None，请务必使用内部辅助函数 dfs 来返回尾节点，不要直接修改主函数的返回类型（除非平台允许）。

将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

# 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 sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        m = len(nums) // 2
        left = self.sortedArrayToBST(nums[:m])
        right = self.sortedArrayToBST(nums[m + 1:])
        return TreeNode(nums[m], left, right)

可将其理解为递归问题，以中间节点为根节点，递归处理左右子树，左右子树同样是二叉搜索树。

二叉树的右视图

给定一个二叉树的 根节点 root ，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

# 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 rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        ans = []
        q = deque([root])
        while q:
            for _ in range(len(q)):
                node = q.popleft()
                if node.left:  q.append(node.left)
                if node.right: q.append(node.right)
            ans.append(node.val)
        return ans

我所能想到的方法就是层序遍历一遍，将每一层的最后一个节点加入结果集。

灵神的解法：

DFS

思路：先递归右子树，再递归左子树，当某个深度首次达到时，对应的节点就在右视图中。

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        def dfs(node: Optional[TreeNode], depth: int) -> None:
            if node is None:
                return
            if depth == len(ans):  # 这个深度首次遇到
                ans.append(node.val)
            dfs(node.right, depth + 1)  # 先递归右子树，保证首次遇到的一定是最右边的节点
            dfs(node.left, depth + 1)
        dfs(root, 0)
        return ans

BFS

只不过用的是两个数组。

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        ans = []
        cur = [root]
        while cur:
            ans.append(cur[-1].val)
            nxt = []
            for node in cur:
                if node.left:  nxt.append(node.left)
                if node.right: nxt.append(node.right)
            cur = nxt
        return ans

从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder:
            return None
        left_size = inorder.index(preorder[0])
        left = self.buildTree(preorder[1:left_size + 1], inorder[:left_size])
        right = self.buildTree(preorder[left_size + 1:], inorder[left_size + 1:])
        return TreeNode(preorder[0], left, right)

递归解法，先递归构造左子树，再递归构造右子树，返回根节点。

根据前序和中序遍历的特点，可以得到根节点的索引，根据索引可以得到左子树的大小，从而递归构造左子树，从而构造右子树。

切片机制详细分析

在 Python 中，列表的切片操作（Slicing，例如 list[start:end]）总是会创建一个新的列表对象，而不是返回原数组的视图或引用。

1. 切片机制： 当你执行 preorder[1:left_size + 1] 或 inorder[:left_size] 时，Python 会在内存中分配新的空间，将原列表中指定范围的元素引用复制到新列表中。

   • 时间开销：切片操作的时间复杂度是 \(O(k)\)，其中 \(k\) 是切片的长度。
   • 空间开销：每次递归都会产生新的列表对象，占用额外的内存。

2. 对算法复杂度的影响： 你提供的这段代码虽然逻辑正确，但效率不是最优的：

   • 时间复杂度：
     • inorder.index(preorder[0]) 需要遍历查找，耗时 \(O(N)\)。
     • 列表切片耗时 \(O(N)\)。
     • 递归每一层都需要做这些操作。在最坏情况下（树退化为链表），总时间复杂度会达到 \(O(N^2)\)。
   • 空间复杂度：
     • 除了递归栈空间 \(O(H)\) 外，由于每次递归都创建新列表，累积的空间开销也会增加，最坏情况下可能达到 \(O(N^2)\)（尽管垃圾回收会及时清理，但峰值内存占用较高）。

优化方案

为了达到 \(O(N)\) 的时间复杂度，通常采用以下两种优化手段：

1. 使用哈希表存储中序遍历的值与索引的映射：避免每次递归都调用 index() 方法查找根节点位置。
2. 使用索引指针代替数组切片：传递原数组的起始和结束下标（start, end），而不是复制子数组。

优化后的代码示例

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        # 1. 构建哈希表，存储 inorder 中值到索引的映射，查找时间降为 O(1)
        inorder_map = {val: idx for idx, val in enumerate(inorder)}
        self.pre_index = 0  # 用于追踪 preorder 当前处理到的根节点

        def helper(left, right):
            if left > right:
                return None

            # 2. 获取当前根节点的值
            root_val = preorder[self.pre_index]
            root = TreeNode(root_val)

            # 3. 根节点索引 +1，处理下一个节点
            self.pre_index += 1

            # 4. 根据哈希表找到根节点在 inorder 中的位置
            index = inorder_map[root_val]

            # 5. 递归构建左右子树，传递索引范围，不复制数组
            root.left = helper(left, index - 1)
            root.right = helper(index + 1, right)

            return root

        return helper(0, len(inorder) - 1)

总结

• 你的代码：每次递归复制新数组。实现简单，但效率较低（\(O(N^2)\)）。
• 优化代码：每次递归传递索引引用。实现稍复杂，但效率最高（\(O(N)\)）。

在面试或高性能场景下，推荐使用优化后的索引法。

路径总和Ⅲ

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 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 = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        # 哈希表记录前缀和出现的次数
        preSum = defaultdict(int)

        # 【关键修正 1】初始化前缀和为 0 的出现次数为 1
        # 这代表“空路径”的和为 0，用于处理从根节点开始的路径
        preSum[0] = 1

        curr_sum = 0  # 当前前缀和
        result = 0    # 结果计数

        def dfs(node: Optional[TreeNode]):
            nonlocal curr_sum, result
            if not node:
                return

            # 1. 更新当前前缀和
            curr_sum += node.val

            # 2. 查找是否存在满足条件的路径
            # 如果 (curr_sum - targetSum) 在 map 中，说明存在子路径和为 targetSum
            result += preSum[curr_sum - targetSum]

            # 3. 将当前前缀和加入 map
            preSum[curr_sum] += 1

            # 4. 递归左右子树
            dfs(node.left)
            dfs(node.right)

            # 5. 【回溯】恢复状态，避免影响其他分支
            preSum[curr_sum] -= 1
            curr_sum -= node.val

        dfs(root)
        return result

我很自然想到了之前的前缀和思路，也就有了上面的解法。不过哈希表的使用还是不够熟练。

二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        result = root
        def dfs(root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> bool:
            nonlocal result
            if root is None:
                return False
            left = dfs(root.left, p, q)
            right = dfs(root.right, p, q)
            if left and right:
                result = root
                return True
            if root is p or root is q:
                if left or right:
                    result = root
                return True
            if left or right:
                return True

        dfs(root, p, q)
        return result

上面是我的解法，但是效率太低了。总结来说就是递归，每次递归都会返回一个布尔值，表示当前节点是否是 p 或 q 的祖先。因为要么是分别在左右子树上，要么其中之一是公共祖先。

优化

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def dfs(node: 'TreeNode') -> 'TreeNode':
            # 基础情况
            if node is None:
                return None

            # 找到 p 或 q，直接返回
            if node is p or node is q:
                return node

            # 递归左右子树
            left = dfs(node.left)
            right = dfs(node.right)

            # 左右都找到，当前节点就是 LCA
            if left and right:
                return node

            # 只找到一边，返回找到的那个
            return left if left else right

        return dfs(root)

场景：p 本身就是 LCA（p 是 q 的祖先）

       3
      / \
     5   1      找 p=5, q=2 的 LCA
    / \
   6   2

期望结果：5（因为 2 在 5 的子树中，5 是最近的公共祖先）

代码执行追踪

def dfs(node):
    if node is None:
        return None
    if node is p or node is q:  # ⭐ 关键行
        return node             # 找到就直接返回，不再向下
    left = dfs(node.left)
    right = dfs(node.right)
    if left and right:
        return node
    return left if left else right

调用栈	执行逻辑	返回值
dfs(3)	不是 p/q → 调用 left=dfs(5), right=dfs(1)	等待...
dfs(5)	node is p → 直接返回 5	5
dfs(1)	不是 p/q → 递归子树 → 都返回 None	None
dfs(3)	left=5, right=None → 返回 left	5 ✅

关键点解析

1. 遇到 p 就停止向下：dfs(5) 不会继续递归 5 的子节点（6 和 2）
2. 向上传递：5 作为返回值传递给父节点 3
3. 另一边没找到：dfs(1) 返回 None
4. 最终判断：left=5, right=None → 返回 5

为什么这样是对的？

• 如果 5 是返回值，说明在 5 的子树中要么找到了另一个目标节点，要么 5 本身就是目标节点之一
• 由于我们找到 p=5 就停止了，如果 q=2 在 5 的子树中，我们不需要再验证，因为题目保证 p 和 q 都存在
• 所以 5 向上传递时，就代表了"5 及其子树包含至少一个目标节点"

---

对比：p 和 q 在不同子树

       3
      / \
     5   1      找 p=5, q=1 的 LCA

调用栈	执行逻辑	返回值
dfs(3)	调用 left=dfs(5), right=dfs(1)	等待...
dfs(5)	node is p → 返回 5	5
dfs(1)	node is q → 返回 1	1
dfs(3)	left=5, right=1 → 都非空，返回 3	3 ✅

---

核心逻辑总结

                    返回节点的含义
                    ↓
        ┌───────────────────────────┐
        │  返回值非空 = 该子树包含   │
        │  p 或 q 中的至少一个       │
        └───────────────────────────┘
                        │
        ┌───────────────┴───────────────┐
        ↓                               ↓
   左右都非空                      只有一边非空
   (p,q 分居两侧)                (p 或 q 在这一侧)
        ↓                               ↓
   当前节点是 LCA              返回非空的那边

三种情况全覆盖

情况	示例	代码行为
p 是 q 的祖先	p=5, q=2	dfs(5) 返回 5，向上传递，最终返回 5
q 是 p 的祖先	p=2, q=5	dfs(5) 返回 5，向上传递，最终返回 5
分居左右子树	p=5, q=1	left=5, right=1，返回根节点 3

---

为什么不需要验证子树？

你可能会想：找到 5 后，不检查它的子树，怎么知道 2 在里面？

答案是：题目保证 p 和 q 都存在于树中。

• 如果 dfs(5) 返回 5，且最终结果是 5，说明另一个目标节点一定在 5 的子树中
• 如果另一个节点不在 5 的子树中，那么 dfs(3) 会收到 left=5, right=1，返回 3 而不是 5

所以这个算法利用了题目约束来简化逻辑，非常巧妙！🎯

验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 严格小于 当前节点的数。
• 节点的右子树只包含 严格大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def dfs(node: Optional[TreeNode], min_val: float, max_val: float) -> bool:
            if not node:
                return True

            # 检查当前节点是否在合法范围内
            if node.val <= min_val or node.val >= max_val:
                return False

            # 递归检查左右子树，更新边界
            return (dfs(node.left, min_val, node.val) and
                    dfs(node.right, node.val, max_val))

        return dfs(root, float('-inf'), float('inf'))

利用递归的思想，检查每一个节点是否符合搜索二叉树的条件。

当然也可以使用中序遍历的方式，中序遍历的结果是递增的，所以只需要检查当前节点的值是否大于前一个节点的值即可。

class Solution:
    pre = -inf
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True
        if not self.isValidBST(root.left):  # 左
            return False
        if root.val <= self.pre:  # 中
            return False
        self.pre = root.val
        return self.isValidBST(root.right)  # 右

二叉搜索树中第 k 个最小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（k 从 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 = right
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        count = 0
        result = 0
        sign = False
        def dfs(root: Optional[TreeNode]):
            nonlocal count, result,sign
            if sign:
                return
            if not root:
                return
            dfs(root.left)
            count += 1
            if count == k:
                result = root.val
                sign = True
            dfs(root.right)
        dfs(root)
        return result

经过上一题，自然而然想到二叉搜素树与中序遍历之间的关系。因此，我采用中序遍历的思路，中序遍历二叉搜索树，找到第 k 小的元素。

二叉树中的最大路径和

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

# 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 maxPathSum(self, root: Optional[TreeNode]) -> int:
        ans = -inf
        def dfs(node: Optional[TreeNode]) -> int:
            if node is None:
                return 0
            l_val = dfs(node.left) # 左子树最大链和
            r_val = dfs(node.right) # 右子树最大链和
            nonlocal ans
            ans = max(ans, l_val + r_val + node.val) # 两条链拼成路径
            return max(max(l_val, r_val) + node.val, 0) # 当前子树最大链和
        dfs(root)
        return ans

同计算最大直径相似，计算包含当前节点的链和最大的链。

图论

岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m = len(grid)
        n = len(grid[0])
        vis = [[False for _ in range(n)] for _ in range(m)]
        def dfs(x: int, y: int):
            if x < 0 or x >= m or y < 0 or y >= n or vis[x][y] or grid[x][y] == '0':
                return
            vis[x][y] = True
            dfs(x + 1, y)
            dfs(x - 1, y)
            dfs(x, y + 1)
            dfs(x, y - 1)
        ans = 0
        for i in range(m):
            for j in range(n):
                if (not vis[i][j]) and grid[i][j] == '1':
                    ans += 1
                    dfs(i, j)
        return ans

其实也就是一个搜索问题，只不过从二叉树变成图了罢了。dfs遍历相邻的位置，这些连接成一片岛屿。

我这里是借助了一个矩阵vis来记录是否访问过，其实也可以就用原本的二维数组来进行标记。

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m = len(grid)
        n = len(grid[0])
        def dfs(x: int, y: int):
            if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] != '1':
                return
            grid[x][y] = '2'
            dfs(x + 1, y)
            dfs(x - 1, y)
            dfs(x, y + 1)
            dfs(x, y - 1)
        ans = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    ans += 1
                    dfs(i, j)
        return ans

遍历过的节点标记为2，这样下次遇到时就不再重复计算。

腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

• 值 0 代表空单元格；
• 值 1 代表新鲜橘子；
• 值 2 代表腐烂的橘子。 每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

from collections import deque
from typing import List

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        queue = deque()
        fresh_count = 0

        # 1. 初始化：将所有初始腐烂橘子入队，统计新鲜橘子数量
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    queue.append((i, j))  # 所有 2 同时入队
                elif grid[i][j] == 1:
                    fresh_count += 1

        # 如果没有新鲜橘子，直接返回 0
        if fresh_count == 0:
            return 0

        minutes = 0
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        # 2. 多源 BFS：所有腐烂源同时扩散
        while queue and fresh_count > 0:
            minutes += 1
            # 处理当前分钟层级所有的腐烂橘子
            for _ in range(len(queue)):
                x, y = queue.popleft()

                for dx, dy in directions:
                    nx, ny = x + dx, y + dy

                    if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:
                        grid[nx][ny] = 2          # 标记为腐烂
                        queue.append((nx, ny))    # 加入队列
                        fresh_count -= 1          # 新鲜橘子减 1

        # 3. 检查是否还有剩余新鲜橘子
        return minutes if fresh_count == 0 else -1

1. 广度优先搜索 (BFS)

本题是典型的 BFS 应用场景。BFS 适用于寻找最短路径或最小步数问题。在网格中，BFS 按“层”向外扩散，每一层代表经过了一分钟。

2. 多源 BFS 模型

与普通 BFS 从单个起点开始不同，本题初始可能有多个腐烂橘子。

• 核心思想：将所有初始腐烂橘子（值为 2）同时加入队列，作为第 0 层。
• 效果：模拟了所有腐烂源“同时”向周围扩散的过程，确保每个新鲜橘子被“最近”的腐烂源感染。

3. 网格遍历与状态管理

• 使用二维数组表示网格。
• 需要记录每个格子的状态（0: 空，1: 新鲜，2: 腐烂）。
• 利用原数组 grid 进行状态标记（将 1 改为 2），可节省额外空间。

实现注意事项

1. 队列的选择

• 推荐：使用 collections.deque。
• 原因：list 的 pop(0) 操作时间复杂度为 O(n)，而 deque 的 popleft() 为 O(1)。在大数据量下，list 会导致超时。

2. 状态标记时机

• 正确做法：在将节点加入队列时，立即标记为已访问（将 grid 改为 2）。
• 错误做法：在从队列取出节点时才标记。这会导致同一节点被多次加入队列，引起内存溢出或重复计算。

3. 时间步数计算

• 时间在每一层扩散完成后增加。
• 常用写法：在 while queue 循环内，先获取当前队列长度 size = len(queue)，然后 for _ in range(size) 处理完当前层所有节点后，minutes += 1。
• 注意：如果最后一层没有感染新橘子，不应增加时间。

常见陷阱与边界情况

1. 串行与并行的误区

• 错误：对每个腐烂橘子单独调用 BFS，最后取最大值。这会导致重复感染且时间计算错误（忽略了同时扩散）。
• 正确：所有初始腐烂橘子一次性入队，统一扩散。

2. 特殊输入处理

• 无新鲜橘子：若初始统计 fresh_count == 0，直接返回 0。
• 无腐烂橘子：若有新鲜橘子但无腐烂橘子，返回 -1。
• 无法全部腐烂：BFS 结束后，若 fresh_count > 0，说明有橘子无法被感染，返回 -1。

3. 内存与性能优化

• 避免使用递归实现 BFS，防止栈溢出。
• 方向数组 dx, dy 预先定义，避免循环内重复创建。
• 及时检查 fresh_count，若为 0 可提前结束循环。

实现Trie(前缀树)

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

• Trie() 初始化前缀树对象。
• void insert(String word) 向前缀树中插入字符串 word 。
• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

class Trie:

    def __init__(self):
        self.root = {}
        self.end = "#"


    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            node = node.setdefault(char, {})
        node[self.end] = None


    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node:
                return False
            node = node[char]
        return self.end in node


    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node:
                return False
            node = node[char]
        return True



# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

嵌套字典的方式进行存储。没太搞懂为什么放在图论这一章节中？因为可以想象成一棵多叉树？

官方解法：

class Trie:
    def __init__(self):
        self.children = [None] * 26
        self.isEnd = False

    def searchPrefix(self, prefix: str) -> "Trie":
        node = self
        for ch in prefix:
            ch = ord(ch) - ord("a")
            if not node.children[ch]:
                return None
            node = node.children[ch]
        return node

    def insert(self, word: str) -> None:
        node = self
        for ch in word:
            ch = ord(ch) - ord("a")
            if not node.children[ch]:
                node.children[ch] = Trie()
            node = node.children[ch]
        node.isEnd = True

    def search(self, word: str) -> bool:
        node = self.searchPrefix(word)
        return node is not None and node.isEnd

    def startsWith(self, prefix: str) -> bool:
        return self.searchPrefix(prefix) is not None

课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        edges = collections.defaultdict(list)
        indeg = [0] * numCourses

        for info in prerequisites:
            edges[info[1]].append(info[0])
            indeg[info[0]] += 1

        q = collections.deque([u for u in range(numCourses) if indeg[u] == 0])
        visited = 0

        while q:
            visited += 1
            u = q.popleft()
            for v in edges[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    q.append(v)

        return visited == numCourses

经典拓扑排序问题，寻找入度为0的节点，并删除该节点的边，更新与之相连的节点的入度。重复此过程，直到所有节点的入度为0。

回溯

回溯算法的标准框架包含以下步骤：

1. 选择：从选择列表中选择一个选项，并将其加入路径。
2. 递归：基于当前选择，继续向前探索，进入下一层递归。
3. 回溯：如果发现当前选择不能得到有效解，或者已经达到边界条件，则撤销这个选择（回溯），返回上一步，尝试其他选项。

特点

• 尝试与撤销：算法会尝试所有可能的步骤来寻找解决方案。如果某步骤不是正确的选择，则撤销这个选择（即回溯），尝试其他选项。这种"试错"机制是回溯法的核心特征。根本是一种暴力枚举的方式。
• 深度优先搜索：回溯算法通常使用深度优先搜索（DFS）策略，这意味着在转向另一种可能之前，它会尽可能深地探索每一种可能，直到找到解或确定无解。
• 适用范围广泛：回溯算法非常适合解决组合问题、约束满足问题等，能够系统地枚举所有可能的解空间。
• 剪枝优化：通过约束条件进行剪枝，可以大幅减少搜索空间，提高算法效率。

全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        results = []
        n = len(nums)
        path = [0] * n
        flag = [False] * n

        def dfs(step: int):
            # nonlocal path  # 删除：不需要
            if step == n:  # step 从 0 开始，等于 n 时结束
                results.append(path[:])  # ✅ 添加拷贝
                return

            for i in range(n):
                if not flag[i]:
                    path[step] = nums[i]  # 不需要减 1
                    flag[i] = True
                    dfs(step + 1)
                    flag[i] = False

        dfs(0)  # 从 0 开始
        return results

列表引用 or 列表拷贝

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        results = []
        n = len(nums)
        path = [0] * n

        flag = [False] * n
        def dfs(step: int):
            nonlocal path
            if step > n:
                results.append(path)
                return
            for i in range(n):
                if not flag[i]:
                    path[step - 1] = nums[i]
                    flag[i] = True
                    dfs(step + 1)
                    flag[i] = False
        dfs(1)
        return results

这段代码有一个 致命错误，会导致所有返回结果都相同。

1. 核心问题：列表引用 vs 列表拷贝

if step > n:
    results.append(path)  # ❌ 错误：添加的是引用
    return

问题说明：

• path 是一个列表对象，append(path) 添加的是 引用（内存地址），不是拷贝。
• 所有 results 中的元素都指向 同一个 path 对象。
• 回溯过程中 path 会被不断修改，最终所有结果都变成 最后一次的状态。

错误演示

# 假设 nums = [1, 2]
# 期望输出：[[1, 2], [2, 1]]
# 实际输出：[[2, 1], [2, 1]]  (所有结果都相同)

✅ 修正方法

if step > n:
    results.append(path[:])  # ✅ 正确：添加拷贝
    # 或 results.append(list(path))
    # 或 results.append(path.copy())
    return

---

2. 次要问题：nonlocal 多余

nonlocal path  # ⚠️ 多余

说明：

• path 是列表（可变对象），在嵌套函数中修改其内容（如 path[step-1] = nums[i]）不需要 nonlocal。
• nonlocal 只用于修改 不可变对象的绑定（如重新赋值 path = []）。
• 这行代码不影响功能，但建议删除。

---

3. 代码风格问题：step 从 1 开始不够直观

dfs(1)  # step 从 1 开始
path[step - 1]  # 需要减 1 转换索引

建议： step 从 0 开始更符合 Python 习惯。

---

✅ 完整修正代码

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        results = []
        n = len(nums)
        path = [0] * n
        flag = [False] * n

        def dfs(step: int):
            # nonlocal path  # 删除：不需要
            if step == n:  # step 从 0 开始，等于 n 时结束
                results.append(path[:])  # ✅ 添加拷贝
                return

            for i in range(n):
                if not flag[i]:
                    path[step] = nums[i]  # 不需要减 1
                    flag[i] = True
                    dfs(step + 1)
                    flag[i] = False

        dfs(0)  # 从 0 开始
        return results

---

4. 问题对比总结

问题	原代码	修正后
结果存储	append(path) 引用	append(path[:]) 拷贝
输出结果	所有结果相同 ❌	每个结果独立 ✅
nonlocal	多余声明	删除
step 起始	从 1 开始，需 step-1	从 0 开始，直接用

---

5. 验证测试

sol = Solution()
print(sol.permute([1, 2, 3]))
# 期望：[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
# 原代码：[[3,2,1], [3,2,1], ...] (全部相同)
# 修正后：正确 ✅

记住：回溯算法中，添加到结果集的可变对象一定要拷贝！

子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

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

        def dfs(step: int):
            if step == n:  # step 从 0 开始，等于 n 时结束
                results.append(path[:])  # ✅ 添加拷贝
                return

            # 选
            path.append(nums[step])
            dfs(step + 1)
            path.pop()
            # 不选
            dfs(step + 1)

        dfs(0)  # 从 0 开始
        return results

每一步选择为是否将当前元素加入子集。

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        results = []
        n = len(digits)
        path = []
        numbers = {}
        numbers[2] = list('abc')
        numbers[3] = list('def')
        numbers[4] = list('ghi')
        numbers[5] = list('jkl')
        numbers[6] = list('mno')
        numbers[7] = list('pqrs')
        numbers[8] = list('tuv')
        numbers[9] = list('wxyz')
        def dfs(step: int):
            if step == n:  # step 从 0 开始，等于 n 时结束
                result = ''.join(path)
                results.append(result)  # 添加字符串
                return

            for i in numbers[int(digits[step])]:
                path.append(i)
                dfs(step + 1)
                path.pop()

        dfs(0)  # 从 0 开始
        return results

一个组合问题，每一步就是选择当前的数字对应的字母。

组合总数

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        results = []
        path = []

        def dfs(start: int, sum0: int):
            if sum0 > target:
                return
            if sum0 == target:
                results.append(path[:])
                return

            # 只使用 for 循环，不混合选/不选分支
            for i in range(start, len(candidates)):
                path.append(candidates[i])
                dfs(i, sum0 + candidates[i])  # 传入 i，允许重复使用当前元素
                path.pop()

        dfs(0, 0)
        return results

本题关键在于，可以重复选用当前元素，因此循环的起始位置 start 允许从当前位置开始。

括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        path = [''] * (n * 2) # 括号大小为 2n

        def dfs(left: int, right: int):
            if right == n: # 填完了
                ans.append(''.join(path))
                return
            if left < n:
                path[left + right] = '('
                dfs(left + 1, right)
            if right < left: # 可以填右括号
                path[left + right] = ')'
                dfs(left, right + 1)

        dfs(0, 0)
        return ans

本质是「选或不选」的思想，你可以把填左括号视作「选」，填右括号视作「不选」。

• 递归的过程中，要保证右括号的个数不能超过左括号的个数。
• 如果现在右括号个数等于左括号个数，那么不能填右括号。
• 如果现在右括号个数小于左括号个数，那么可以填右括号。
• 由于左括号个数始终 ≥ 右括号个数，且至多填 n 个左括号，所以当我们填了 n 个右括号时，也一定填了 n 个左括号，此时填完所有 2n 个括号。

由于结果恒定为2n长度，直接覆盖即可，无需进行恢复现场操作。

单词搜索

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m = len(board)
        n = len(board[0])
        flag = [[False for _ in range(n)] for _ in range(m)]
        result = False

        def dfs(step: int, x: int, y: int):
            nonlocal result
            if step > len(word):
                return
            if step == len(word):
                result = True
                return
            if x < 0 or x >= m or y < 0 or y >= n:
                return
            if not flag[x][y] and word[step] == board[x][y]:
                flag[x][y] = True
                dfs(step + 1, x - 1, y)
                dfs(step + 1, x + 1, y)
                dfs(step + 1, x, y - 1)
                dfs(step + 1, x, y + 1)
                flag[x][y] = False
            else:
                return

        for i in range(m):
            for j in range(n):
                if result:
                    return result
                if not flag[i][j]:
                    dfs(0, i, j)

        return result

我个人的思路比较简单，就是看你选不选当前元素。

二维数组初始化

在 Python 中，快速初始化二维数组有多种方式，具体取决于你使用的是原生嵌套列表还是第三方库如 NumPy。以下是常见且高效的初始化方法：

---

1. 使用列表推导式（推荐）

# 创建 3 行 4 列，初始值为 0
array = [[0 for _ in range(4)] for _ in range(3)]

# 初始化为其他值
array = [[1 for _ in range(4)] for _ in range(3)]

# 初始化为行列索引
array = [[i * j for j in range(4)] for i in range(3)]

2. 使用乘法（⚠️ 慎用）

# ❌ 错误方式：所有行引用同一对象
array = [[0] * 4] * 3
array[0][0] = 1
print(array)  # [[1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]

# ✅ 正确方式：每行独立
array = [[0] * 4 for _ in range(3)]
array[0][0] = 1
print(array)  # [[1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

n皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        # selected[i]表示第i行的皇后放在第selected[i]的位置
        selected = [-1] * n
        results = []
        def dfs(step: int):
            if step == n:
                results.append(['.' * c + 'Q' + '.' * (n - 1 - c) for c in selected])
                return

            # 开始搜索，判断第step行的皇后能否放在第i列
            for i in range(n):
                can_place = True
                for j in range(step):
                    if selected[j] == i or abs(selected[j] - i) == abs(j - step):
                        can_place = False
                        break
                if can_place:
                    # 直接覆盖即可，无需恢复现场
                    selected[step] = i
                    dfs(step + 1)
        dfs(0)
        return results

基本思路：递归放置每一行，直到放置完成。

可采用辅助数组进行优化：

from typing import List

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        selected = [-1] * n
        results = []

        col_used = [False] * n
        main_diag_used = [False] * (2 * n)    # 主对角线：row - col + n
        anti_diag_used = [False] * (2 * n)    # 副对角线：row + col

        def dfs(row: int):
            if row == n:
                results.append(['.' * c + 'Q' + '.' * (n - 1 - c) for c in selected])
                return

            for col in range(n):
                d_main = row - col + n   # ✅ 主对角线索引（↘️）
                d_anti = row + col        # ✅ 副对角线索引（↙️）

                if not col_used[col] and not main_diag_used[d_main] and not anti_diag_used[d_anti]:
                    selected[row] = col
                    col_used[col] = True
                    main_diag_used[d_main] = True
                    anti_diag_used[d_anti] = True

                    dfs(row + 1)

                    # 回溯：恢复状态
                    col_used[col] = False
                    main_diag_used[d_main] = False
                    anti_diag_used[d_anti] = False

        dfs(0)
        return results

可以观察到，同一列、同一主副对角线元素均满足某些条件，因此可以利用辅助数组进行优化。

二分查找

二分查找是一种常用的搜索算法，它的时间复杂度是 \(O(log n)\)。

注意一定要是有序数组，二分思维的精髓是通过已知信息尽可能地收缩折半搜索空间。

可以将搜索区间全部统一为两端都是闭区间。

搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 \(O(log n)\) 的算法。

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # 闭区间写法
        left, right = 0, len(nums) - 1
        # 区间不为空
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1
        return left

搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # 闭区间写法
        left, right = 0, len(matrix) - 1
        # 区间不为空
        while left <= right:
            mid = left + (right - left) // 2
            if matrix[mid][0] == target:
                return True
            elif matrix[mid][0] > target:
                right = mid - 1
            elif matrix[mid][0] < target:
                left = mid + 1
        # 闭区间写法
        left = left - 1
        left_0, right_0 = 0, len(matrix[0]) - 1
        # 区间不为空
        while left_0 <= right_0:
            mid = left_0 + (right_0 - left_0) // 2
            if matrix[left][mid] == target:
                return True
            elif matrix[left][mid] > target:
                right_0 = mid - 1
            elif matrix[left][mid] < target:
                left_0 = mid + 1
        return False

矩阵的每一行都按照升序排列，每一列也按照升序排列。于是乎我先对每一行的首元素进行二分查找，找到对应的所在行，再进行按照行元素的升序查找。

在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

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

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        result = [-1, -1]
        if not nums:
            return result
        # 闭区间写法
        left, right = 0, len(nums) - 1
        # 区间不为空
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] >= target:
                right = mid - 1
        if left >= len(nums):
            return result
        if nums[left] == target:
            result[0] = left
        while left < len(nums) and nums[left] == target:
            result[1] = left
            left += 1

        return result

上述是我的解法，但考虑到最极端的情况，查找最后一个位置的复杂度为 \(O(n)\)，因此还需要使用二分查找进行优化。

灵神的解法：

class Solution:
    # lower_bound 返回最小的满足 nums[i] >= target 的下标 i
    # 如果数组为空，或者所有数都 < target，则返回 len(nums)
    # 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
    def lower_bound(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1  # 闭区间 [left, right]
        while left <= right:  # 区间不为空
            # 循环不变量：
            # nums[left-1] < target
            # nums[right+1] >= target
            mid = (left + right) // 2
            if nums[mid] >= target:
                right = mid - 1  # 范围缩小到 [left, mid-1]
            else:
                left = mid + 1  # 范围缩小到 [mid+1, right]
        # 循环结束后 left = right+1
        # 此时 nums[left-1] < target 而 nums[left] = nums[right+1] >= target
        # 所以 left 就是第一个 >= target 的元素下标
        return left

    def searchRange(self, nums: List[int], target: int) -> List[int]:
        start = self.lower_bound(nums, target)
        if start == len(nums) or nums[start] != target:
            return [-1, -1]  # nums 中没有 target
        # 如果 start 存在，那么 end 必定存在
        end = self.lower_bound(nums, target + 1) - 1
        return [start, end]

依旧使用二分查找找寻左端点，找寻右端点的过程改为查找比该元素大1的元素应该在的位置，然后减1得到该元素最有一个元素在数组中的索引。

搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 向左旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 下标 3 上向左旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 \(O(log n)\) 的算法解决此问题。

from typing import List

class Solution:
    def lower_bound(self, nums: List[int], target: int, k: int) -> int:
        """在旋转数组中找第一个 >= target 的位置（虚拟展开数组二分）"""
        n = len(nums)
        left, right = k, n - 1 + k  # 虚拟数组区间 [k, k+n-1]

        while left <= right:
            mid = (left + right) // 2
            # 通过取模映射回原数组
            if nums[mid % n] >= target:
                right = mid - 1
            else:
                left = mid + 1
        # left 是虚拟数组中第一个 >= target 的位置，映射回原数组
        return left % n

    def search(self, nums: List[int], target: int) -> int:
        if not nums:  # 🔥 修复空数组崩溃
            return -1

        # 步骤 1: 找旋转点（最小值索引）
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid
        pivot = left  # 最小值位置

        # 步骤 2: 在虚拟展开数组中二分查找
        idx = self.lower_bound(nums, target, pivot)

        # 步骤 3: 验证是否真的找到
        return idx if nums[idx] == target else -1

注意事项

寻找旋转数组最小值的标准二分的正确写法：

# 找旋转点（最小值索引）
left, right = 0, len(nums) - 1
while left < right:  # ✅ 用 < 而不是 <=
    mid = (left + right) // 2
    if nums[mid] > nums[right]:
        # 最小值一定在右半部分 (mid+1 ~ right)
        left = mid + 1
    else:
        # 最小值在左半部分，且 mid 本身可能是最小值
        right = mid  # ✅ 不能 -1！
# 循环结束时 left == right，即为最小值位置
pivot = left

当比较对象是 nums[right] 时：

• 如果 nums[mid] > nums[right] → 最小值在右侧 → left = mid + 1
• 否则（nums[mid] <= nums[right]）→ 最小值在左侧且可能是 mid → right = mid
• 循环条件用 left < right，结束时 left==right 即为答案

不使用虚拟数组

from typing import List

class Solution:
    def lower_bound(self, nums: List[int], target: int, left: int, right: int) -> int:
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] >= target:
                right = mid - 1
            else:
                left = mid + 1
        return left

    def search(self, nums: List[int], target: int) -> int:
        if not nums:  # 🔥 修复空数组崩溃
            return -1

        # 步骤 1: 找旋转点（最小值索引）
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid
        pivot = left  # 最小值位置
        # 步骤 2: 查找
        if nums[-1] >= target:
            idx = self.lower_bound(nums, target, pivot, len(nums) - 1)
        else:
            idx = self.lower_bound(nums, target, 0, pivot - 1)
        # 步骤 3: 验证是否真的找到
        return idx if idx < len(nums) and nums[idx] == target else -1

找到旋转点后，其实就可以知道具体是在哪一段上找了，在对应的一段上进行二分查找即可。

寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到： 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2] 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7] 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[-1]:
                left = mid + 1
            else:
                right = mid
        pivot = left  # 最小值位置
        return nums[pivot]

其实也就是寻找旋转点，不过返回的是最小值，而不是索引。

寻找两个正序数组的中位数

🔍 寻找两个正序数组的中位数 - 通俗解法

💡 一句话理解：中位数就是把两个数组切成左右两半，使得 左边所有数 ≤ 右边所有数，且左右元素个数相等（或差1）。

示例：nums1 = [1,3], nums2 = [2]

合并后：[1, 2, 3]，中位数是 2

用“分割线”视角：
nums1: [1 | 3]     ← 在索引1处切一刀
nums2: [  | 2]     ← 在索引0处切一刀

左边部分：[1] + [] = [1]      → 最大值 = 1
右边部分：[3] + [2] = [2,3]   → 最小值 = 2

✅ 满足：左边最大值(1) ≤ 右边最小值(2)
✅ 左边元素个数 = 1，右边 = 2（总长度3，允许差1）
→ 中位数 = 右边最小值 = 2

🎯 核心思想：找“分割线”，而不是合并数组

传统做法是合并两个数组再找中位数，时间复杂度 O(m+n)，不满足题目 O(log(m+n)) 的要求。 本题的最优解是 二分查找分割点。我们不需要真正合并数组，只需要在两个数组中各找一条“分割线”，使得：

1. 分割线左侧的元素总数 = 右侧元素总数（或左侧多1个）
2. 左侧的最大值 ≤ 右侧的最小值

🧠 算法步骤（通俗版）

1. 选短数组二分：在长度较小的数组上二分查找分割点 i，保证时间复杂度为 O(log(min(m,n)))。
2. 自动计算另一个分割点：j = (m + n + 1) // 2 - i。这个公式保证了左右两侧元素个数平衡。
3. 获取关键值：分割线会把数组切成四块，我们需要关注紧挨着分割线的四个值：
   • max_left1（nums1左侧最大值）
   • min_right1（nums1右侧最小值）
   • max_left2（nums2左侧最大值）
   • min_right2（nums2右侧最小值） (边界处理：越界时用 -∞ 或 +∞ 代替)
4. 检查分割是否合法：必须满足 max_left1 <= min_right2 且 max_left2 <= min_right1。
5. 调整二分边界：
   • 如果 max_left1 > min_right2 → nums1 左边太大，分割点 i 需左移 (right = i - 1)
   • 否则 → nums1 左边太小，分割点 i 需右移 (left = i + 1)
6. 计算中位数：
   • 总长度为奇数：max(max_left1, max_left2)
   • 总长度为偶数：(max(max_left1, max_left2) + min(min_right1, min_right2)) / 2

✅ Python 代码（带详细注释）

from typing import List

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # 🔥 保证 nums1 是较短的数组，减少二分次数
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1

        m, n = len(nums1), len(nums2)
        left, right = 0, m  # 在 nums1 的 [0, m] 范围内二分分割点

        while left <= right:
            # nums1 的分割点 i：左边有 i 个元素
            i = (left + right) // 2
            # nums2 的分割点 j：保证左边总元素 = (m+n+1)//2
            j = (m + n + 1) // 2 - i

            # 🎯 获取分割线左右的4个关键值（处理边界用 ±inf）
            max_left1 = float('-inf') if i == 0 else nums1[i-1]
            min_right1 = float('inf') if i == m else nums1[i]

            max_left2 = float('-inf') if j == 0 else nums2[j-1]
            min_right2 = float('inf') if j == n else nums2[j]

            # ✅ 找到合法分割：左边最大值 ≤ 右边最小值
            if max_left1 <= min_right2 and max_left2 <= min_right1:
                # 总长度奇数：中位数是左边最大值
                if (m + n) % 2 == 1:
                    return max(max_left1, max_left2)
                # 总长度偶数：中位数是左右极值的平均
                else:
                    return (max(max_left1, max_left2) + min(min_right1, min_right2)) / 2

            # ❌ 分割不合法，调整二分边界
            elif max_left1 > min_right2:
                # nums1 左边太大，分割点 i 要左移
                right = i - 1
            else:
                # nums1 左边太小，分割点 i 要右移
                left = i + 1

        return 0.0

🧪 手动模拟示例

示例 1： nums1 = [1,3], nums2 = [2]

m=2, n=1, 总长=3（奇数），左边需要 (3+1)//2 = 2 个元素
初始: left=0, right=2
① i=1, j=2-1=1
   nums1: [1 | 3], nums2: [2 | ]
   max_left1=1, min_right1=3
   max_left2=2, min_right2=+∞
   检查: 1≤∞ ✅, 2≤3 ✅ → 找到合法分割！
   中位数 = max(1,2) = 2 ✅

示例 2： nums1 = [1,2], nums2 = [3,4]

m=2, n=2, 总长=4（偶数），左边需要 (4+1)//2 = 2 个元素
① i=1, j=2-1=1
   nums1: [1 | 2], nums2: [3 | 4]
   max_left1=1, min_right1=2
   max_left2=3, min_right2=4
   检查: 1≤4 ✅, 但 3≤2 ❌ → 不合法！
② 因为 max_left2(3) > min_right1(2)，说明 nums2 左边太大
   → 需要让 nums1 左边多拿元素 → i 右移 → left = 2
③ i=2, j=2-2=0
   nums1: [1,2 | ], nums2: [ | 3,4]
   max_left1=2, min_right1=+∞
   max_left2=-∞, min_right2=3
   检查: 2≤3 ✅, -∞≤∞ ✅ → 合法！
   中位数 = (max(2,-∞) + min(∞,3)) / 2 = (2+3)/2 = 2.5 ✅

📊 复杂度分析

项目	复杂度	说明
时间	O(log(min(m,n)))	在较短的数组上二分，每次检查 O(1)
空间	O(1)	仅使用常数个额外变量

💡 记忆口诀 & 避坑指南

🔹 核心公式

• 二分对象：永远选短数组，分割点范围 [0, m]（包含两端！）
• 互补公式：j = (m + n + 1) // 2 - i （+1 保证奇数总长时左侧多1个元素）
• 边界处理：用 ±inf 代替 if 越界判断，代码更优雅
• 合法条件：max_left1 <= min_right2 且 max_left2 <= min_right1（必须双向检查）
• 调整方向：max_left1 > min_right2 → i 左移；否则 → i 右移

🚫 常见错误

# ❌ 错误1：j 的计算漏了 +1，导致奇数时左右不平衡
j = (m + n) // 2 - i

# ❌ 错误2：边界没处理，直接取值导致 IndexError
max_left1 = nums1[i-1]  # i=0 时越界！

# ❌ 错误3：只检查一边，导致分割线交叉
if max_left1 <= min_right2:  # 漏了 max_left2 <= min_right1！

🎁 附：更简洁的写法（进阶）

逻辑完全一致，去除了冗余注释，适合面试快速手写：

def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
    A, B = nums1, nums2
    if len(A) > len(B):
        A, B = B, A
    m, n = len(A), len(B)

    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2
        j = (m + n + 1) // 2 - i

        A_left = A[i-1] if i > 0 else float('-inf')
        A_right = A[i] if i < m else float('inf')
        B_left = B[j-1] if j > 0 else float('-inf')
        B_right = B[j] if j < n else float('inf')

        if A_left <= B_right and B_left <= A_right:
            if (m + n) % 2:
                return max(A_left, B_left)
            return (max(A_left, B_left) + min(A_right, B_right)) / 2
        elif A_left > B_right:
            hi = i - 1
        else:
            lo = i + 1