DFS

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

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