中序遍历

这篇是我重做 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. ...

这篇是我刷 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]。节点按中序位置从左到右排开，所以屏幕上从左到右就是从小到大。 ...