LeetCode

这篇是我重做 230. Kth Smallest Element in a BST · 二叉搜索树中第 K 小的元素 时整理的笔记。上一篇用的是 nonlocal 加剪枝的写法，这次换成 self.k、不剪枝的写法，重点看递归到底按什么顺序执行。 These are my notes from redoing LeetCode 230. The previous post used nonlocal with pruning. This time I use self.k with no pruning, and focus on the exact order in which the recursion runs. 一句话总结本质： 二叉搜索树（BST）的中序遍历（in-order traversal）是升序，所以每个节点在自己的调用里把 k 减 1，减到 0 的那个节点就是第 k 小。 In one sentence: A BST’s in-order traversal is ascending, so each node decrements k once, inside its own call, and the node that brings k to 0 is the k-th smallest. ...

这篇是我做 78. Subsets · 子集 时整理的回溯（backtracking）笔记。一开始我能背模板，但说不清 path.pop() 到底在干嘛、为什么子集不会重复。后来配合动画一步步走，才真的看懂。 This is my note on backtracking, written while working on LeetCode 78 Subsets. At first I could recite the template, but I couldn’t explain what path.pop() was actually doing, or why subsets never come out duplicated. Stepping through it with animations is what finally made it click. 一句话总结本质： 回溯就是在一棵决策树上做 DFS。每走一步都是三件事：做选择（append）→ 往下走（递归）→ 撤销选择（pop）。撤销是为了回到岔路口，让下一个选项拿到一条干净的 path。 Backtracking is DFS on a decision tree. Every step is three moves: choose (append) → explore (recurse) → un-choose (pop). Un-choosing walks you back to the fork, so the next option starts from a clean path. ...

这篇接着上一篇 回溯学习笔记。我在给 nums = [1,2,3,4] 画 78. Subsets 的递归树时，好几次把节点和循环对错了位置，比如把 range(2,4) 安到 [1,2,3] 头上。这篇把怎么对齐整理清楚。 This follows my earlier backtracking note. While drawing the recursion tree of LC 78 Subsets for nums = [1,2,3,4], I kept attaching loops to the wrong nodes, for example putting range(2,4) on [1,2,3]. This note is about how to line them up. 一句话总结： 节点的 start 是几，它自己的循环就是 range(几, 4)。 循环里的每个 i 产生一个孩子，孩子的 start 是 i + 1。 A node’s own loop always uses its own start: range(start, 4). Each i in that loop makes one child, and that child’s start is i + 1. ...

这篇是我做 124. Binary Tree Maximum Path Sum · 二叉树中的最大路径和 时整理的笔记。卡住我的不是公式，而是递归到底按什么顺序走。 This is a note from working on LeetCode 124. What tripped me up wasn’t the formula. It was the order the recursion actually runs in. 一句话总结本质： 每进入一个节点，先一路往左钻到底；左边返回后，同一个节点才去右边；进了右子树，又重新「先左后右」。两边都返回后，才处理自己。完整规则：左 → 右 → 自己（后序遍历，post-order）。 Every time you enter a node, you dive all the way left first. Once the left side returns, that same node goes right. Inside the right subtree, “left first, then right” starts over. Only after both sides return does the node process itself. The full rule: left → right → self (post-order). ...

这篇是我刷 230. Kth Smallest Element in a BST · 二叉搜索树中第 K 小的元素 时整理的笔记。重点不在代码多难，而在于亲眼看着递归一步步走，搞清楚它什么时候往右走、什么时候停。 一句话总结本质： 二叉搜索树（BST）的中序遍历（in-order traversal）就是升序，所以按中序数到第 k 个节点，它就是第 k 小。 一、为什么中序遍历 = 升序 BST 的规则是：左子树所有值 < 根 < 右子树所有值。中序遍历的顺序是左 → 根 → 右，正好把这条规则从小到大"读"出来。 所以不用排序、不用存数组，只要边遍历边倒数：每访问一个节点就 k -= 1，k 变成 0 的那个节点就是答案。 二、代码 class Solution: def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: ans = None def dfs(node): nonlocal k, ans if not node: return dfs(node.left) if k == 0: return # found on the left k -= 1 # visit node if k == 0: ans = node.val return dfs(node.right) dfs(root) return ans 几个关键行： dfs(node.left)：先一路往左钻到最小值。 k -= 1：这就是"访问"当前节点，相当于数了一个。 if k == 0: ans = node.val：数够了，记答案。 if k == 0: return（紧跟在 dfs(node.left) 后面）：剪枝（pruning），左边已经找到答案了，当前节点和右边都不用看。 三、逐步图解（可以点） 用题目示例的树 [5,3,6,2,4,null,null,1]。节点按中序位置从左到右排开，所以屏幕上从左到右就是从小到大。 ...