LeetCode-337这道题我第一次做的时候还没反应过来它是道树形DP直到用带爷爷节点的递归被一个大样例卡到超时才意识到二叉树的“树形”不只是换了一层壳。打家劫舍Ⅲ是打家劫舍系列的第三弹前面的数组和环形都是一条线到这儿突然变成一个二叉树相邻节点不能同时偷题意一句话就能看懂但怎么把“相邻”转换成状态转移是很多人卡住的地方。今天就把这道题从暴力递归到树形DP再到迭代法完整拆开讲一遍顺便聊几个我实际调试时踩过的坑。1. 先看清楚题目在说什么树上的“相邻”和线性的“相邻”完全不同1.1 从打家劫舍Ⅰ到Ⅲ状态定义跟着数据结构走打家劫舍Ⅰ是最简单的线性DP一条街上挨着的两户不能同时偷用一个一维数组就能解决状态只需要记录“当前位置偷不偷”。打家劫舍Ⅱ加了一个环麻烦在首尾相连但也只是多考虑两种起点情况。到了打家劫舍Ⅲ输入直接从数组变成二叉树很多人的第一反应是“这不就是把层序遍历出来再做一次线性DP吗”这个思路我一开始也动过但很快就发现行不通。为什么行不通线性结构里每个位置只有前后两个邻居冲突关系是链式的而二叉树里每个节点有父节点和左右孩子虽然局部关系也是“相邻不能同时偷”但整棵树的冲突关系不是一条链而是分叉的。更重要的是兄弟节点之间没有约束根节点偷了左孩子和右孩子都不能偷但这左右孩子本身不存在先后顺序上的耦合所以问题天然可以拆成左子树和右子树两个独立子问题。这个“独立”二字就是树形DP能成立的前提。从状态定义的角度看前两题的状态是“dp[i]表示前i家能偷到的最大金额”而第三题不能再按数组下标来定义因为树没有下标。你要么给每个节点定义状态要么让递归的返回值携带状态。很多教程上来就说“每个节点返回偷和不偷两个值”但没讲清楚为什么是两个值以及这两个值是怎么从“父子冲突”这个约束里长出来的。其实很简单站在某个节点上影响它决策的唯一外部因素就是它父节点有没有被偷。父节点偷了它自己就必须是被跳过的那条分支父节点没偷它自己偷不偷都能选。所以每个节点只需要回答两个问题我偷能带给我多少收益我不偷能带给我多少收益。1.2 树上的局部关系只约束父子不约束兄弟很多第一次接触树形DP的人会被“相邻节点”这句话误导以为还要考虑节点之间的距离、层级甚至去遍历每个节点的所有邻居。实际上这道题里“相邻”只有一种情况父子节点。兄弟节点之间没有任何约束。这个性质直接决定了状态转移的范围——你只需要看左右两个子树而不需要跨子树去查别的关系。我拿最简单的三层树举例根节点值为3左右儿子分别为2和3左儿子的右儿子是3右儿子的右儿子是1。这个用例是题目给的官方示例根节点和左儿子的右儿子、右儿子的右儿子之间隔了一层它们一起偷是合法的。如果你把“相邻”理解成“同一层兄弟也不能偷”就会得出完全错误的答案。所以拿到题目先别急着写代码先在纸上把“谁不能跟谁同时选”这个关系圈出来树形DP的转移方程基本就藏在这个关系图里。2. 暴力递归为什么慢把“爷爷偷不偷”放进参数里的代价2.1 爷爷带孙子的经典超时写法我最初提交过一个非常朴素的递归版本思路是枚举当前节点偷不偷。如果偷当前节点那么它的两个孩子不能偷但是四个孙子左孩子的左右孩子、右孩子的左右孩子可以偷所以收益是“当前节点值 四个孙子子问题的最优解之和”如果不偷当前节点那么两个孩子都可以偷收益是“两个孩子子问题的最优解之和”。代码写出来是这样的def rob(root): if root is None: return 0 # 偷当前节点 money root.val if root.left: money rob(root.left.left) rob(root.left.right) if root.right: money rob(root.right.left) rob(root.right.right) # 不偷当前节点 money2 rob(root.left) rob(root.right) return max(money, money2)这个写法思路其实很直观完全是按题意模拟的但一提交就超时。原因有两个一是同一个节点会被不同的调用路径重复计算很多次。比如节点A在不偷父节点时会被计算一遍在偷父节点时又会通过“孙子”路径被计算一遍甚至同一个节点可能同时成为不同祖先的孙子导致重复次数指数增长。二是递归的分支数量跟树的深度呈斐波那契级别膨胀树一深计算量直接爆炸。我给一个具体例子一条单链树每个节点只有一个左孩子深度到20层。用这个暴力递归去跑它的计算量会接近2^n树稍微深一点就卡死。你可能会说“加个缓存不就行了”对暴力递归加lru_cache确实能过但它过得很勉强而且暴露了一个更重要的问题我们是在枚举策略不是在动态规划。真正的树形DP应该让每个节点只回答一次“我偷或不偷能带来多少钱”而不是让同一个节点在多种不同场景里反复被询问。2.2 为什么说暴力递归的“参数”设计是问题根源你仔细看暴力递归的参数它其实是把“场景选择”外置了通过递归到不同子节点来区分“当前节点是作为孙子被调用的”还是“作为孩子被调用的”。这种设计的本质问题是状态变量握在了调用方手里而不是由节点自己决定。于是同一个子树、同一个根节点会因为父节点的不同状态而产生两套甚至多套计算路径而这些路径之间又缺少统一的合并逻辑。正确的做法应该是把决策权下放给每个节点每个节点都基于自己的左右子树返回值独立算出“我偷”和“我不偷”两种结果然后由父节点来选择用哪一种。父节点不需要知道子树的内部结构只需要拿到这两个数字。这样做的好处是每个节点只被递归访问一次没有重复子问题也不需要额外的缓存。这也是动态规划里很常见的一个思想把“决策”从“枚举场景”里剥离出来只保留真正影响结果的那个状态维度。3. 树形DP的核心设计每个节点返回“偷”和“不偷”两个结果3.1 状态定义与转移方程推导现在开始正经的树形DP。定义steal(node)表示偷node这个节点时以node为根的整棵子树能获得的最大收益定义skip(node)表示不偷node时同一棵子树能获得的最大收益。那么当node被偷时左右两个孩子都绝对不能偷所以steal(node) node.val skip(node.left) skip(node.right)当node不被偷时左右孩子没有来自父节点的限制每个孩子都可以在“偷”和“不偷”里选收益更大的那个所以skip(node) max(steal(node.left), skip(node.left)) max(steal(node.right), skip(node.right))这两个方程就是整道题的全部核心。第一个方程的推导逻辑是父子冲突第二个方程的推导逻辑是兄弟独立。很多人会问为什么skip里不是直接加两个steal因为孩子如果是独立自由的话它完全可能选择不偷你强行让孩子偷反而会丢失更优解。只有让它自由选择才能保证全局最优。还有一点必须强调这里的计算顺序是后序遍历。因为要算出某个节点的steal和skip必须先知道它左右子树的返回值。所以递归函数的执行顺序是先递归左子树再递归右子树最后计算当前节点。如果你用前序或者中序去算当前节点拿到的是未完成的子树结果算出来一定是错的。3.2 递归代码实现与复杂度分析代码实现其实非常短短到很多人第一次看会怀疑“这么点代码就够了吗”。确实够了算法题的魅力就在这逻辑越清晰代码越简洁class Solution: def rob(self, root: Optional[TreeNode]) - int: def dfs(node): if not node: return 0, 0 left_steal, left_skip dfs(node.left) right_steal, right_skip dfs(node.right) # 偷当前节点 steal node.val left_skip right_skip # 不偷当前节点 skip max(left_steal, left_skip) max(right_steal, right_skip) return steal, skip steal_root, skip_root dfs(root) return max(steal_root, skip_root)注意这里返回的是一个二元组第一个是偷当前节点的最大收益第二个是不偷当前节点的最大收益。最后根节点的答案是两者取大因为根节点没有父节点管着它偷不偷都行。这个版本的时间复杂度是O(n)因为每个节点只被递归访问一次每次做常数次运算。空间复杂度是O(height)height是树的高度递归栈最深也就到树高。对于一棵完全随机生成的二叉树高度是log级别空间占用很安全但如果是一棵极度倾斜的链状树递归深度可能到几万层这时候确实要考虑栈溢出的问题后面我会讲怎么用栈模拟解决。4. 记忆化与迭代手段哪些优化真有意义哪些是画蛇添足4.1 双状态递归里加缓存真没必要我在社群里看到很多人写这题时会在dfs上加一个lru_cache然后问我“这样是不是更稳”。我的回答是这版递归压根没有重复子问题加缓存纯属多此一举。每个节点只会被访问一次缓存表的查询和写入反而增加了常数时间开销。之所以有人下意识加缓存是因为他们之前写过暴力递归版本被那个版本的重复计算吓怕了惯性思维。缓存在这道题里真正有意义的是暴力递归版本。如果你坚持用“爷爷带孙子”那种写法每个节点会在不同场景下被重复递归这时加缓存能把它从指数级拉回到多项式级。但我要提醒你这属于“优化一个不够好的算法”投入产出比很低。既然状态转移方程已经告诉我们该返回两个值就没必要绕远路。判断一个DP递归要不要加缓存标准只有一个是否存在重叠子问题。在这道双状态递归里每个节点对应唯一的状态不存在重叠所以不需要。4.2 想彻底避开递归用栈模拟后序遍历如果树的深度太深或者你所在的技术栈对递归栈深度有限制可以用手动栈模拟后序遍历。这个思路和“快速排序非递归”是同一套东西递归本质上就是用函数调用栈保存现场你不想用系统栈就自己用显式栈来模拟。后序遍历的难点在于你第一次经过一个节点时还不能算它必须等左右子树都算完再回头处理它。所以通常需要在节点入栈时打一个标记或者用一个额外的状态区分“第一次访问”和“第二次访问”。def rob_iterative(root): if not root: return 0 stack [(root, False)] result {} # 用字典保存每个节点返回的(steal, skip) while stack: node, visited stack.pop() if node is None: continue if visited: left_steal, left_skip result.get(node.left, (0, 0)) right_steal, right_skip result.get(node.right, (0, 0)) steal node.val left_skip right_skip skip max(left_steal, left_skip) max(right_steal, right_skip) result[node] (steal, skip) else: # 第二次访问时计算 stack.append((node, True)) # 后序先压右孩子再压左孩子 if node.right: stack.append((node.right, False)) if node.left: stack.append((node.left, False)) return max(result[root])这个版本里每个节点在第一次出栈时会把左右孩子压栈然后再把自己以visitedTrue状态压回去等第二次弹出时它的左右子树结果已经存在result里了可以直接计算。时间复杂度和递归版一样是O(n)空间复杂度是O(n)因为要存result字典和栈。说实话在LeetCode的测试数据里递归版完全够用我写迭代版主要是为了展示“递归转迭代”的一般套路——手动维护一个状态栈用标记位模拟递归函数里的两条路径。这个技巧刷题时掌握一下非常有价值很多“非递归实现”的题都是这个思路。你想想快速排序的非递归实现不也是用一个栈保存待排序区间的左右边界吗树的递归改迭代栈里保存的是节点和访问状态套路完全一样。5. 实战踩坑记录写这道题最容易翻车的几个地方5.1 返回值的顺序别搞反dfs返回的二元组我建议固定成(steal, skip)也就是“偷当前节点的收益”放前面“不偷当前节点的收益”放后面。很多人写着写着就变成先返回skip再返回steal结果转移方程里left_skip取到的是steal整个树的结果全错。更坑的是这种错很隐蔽小用例可能碰巧对大用例死活不过。我现在的习惯是先把注释写在函数第一行返回 (偷当前节点收益, 不偷当前节点收益)这样就算过两周再回来看代码也不会搞错。调试的话可以用一个只有三个节点的树根节点3左孩子2右孩子3。手算一下最优是偷根节点和右孩子总收益6然后看程序输出是不是6。5.2 空节点的返回值是(0, 0)不是直接结束递归里遇到None节点要返回(0, 0)代表一个空子树偷和不偷都是0。这个看起来很自然但初学者容易犯错的是在dfs的开始直接return 0这样返回的是单个整数而不是二元组后面解包就会报错。还有一种错误是把None节点当作“必须不偷”返回(0, -inf)之类的东西这也是不对的。空树没有节点也不存在任何收益两种情况都是0仅此而已。5.3 别用“按层取和”再套线性DP我在社区里见过一种思路把二叉树每一层的节点值加起来变成一个新的数组然后对这个数组跑一遍打家劫舍Ⅰ。这看起来很有道理因为“不能偷同一层”听起来好像跟“不能偷相邻层”有关系但实际上是错的。同一层的节点之间没有任何约束兄弟节点是可以同时偷的而不同层的节点也可能因为父子关系而不能同时偷。比如一个三层树第一层偷了第二层就不能偷但第三层的所有节点都可以偷如果你按层取和得到的是第一层和第三层的和看起来没问题但第二层内部如果有多个节点它们完全可以一起被偷只是它们的父节点不能偷。按层取和会让这些兄弟之间的独立性丢失导致结果偏低或偏高完全不可控。想验证的话可以构造一个根节点很小、两个孩子很大的树按层贪心会优先取第二层但如果第二层的某个孩子下面又有一个很大的孙子呢按层就干扰了。所以结论是树形DP就是树形DP别强行降维成线性。5.4 递归调试的土办法打印返回值递归函数不好调试尤其是树上递归一旦出错很难定位是哪个子树算错了。我的土办法是在每个节点返回前打印node.val和两个返回值然后跑一个小样例手动验证每一层的值是否符合预期。比如root的返回值应该是“偷根”等于根值加两个孩子的skip“不偷根”等于两个孩子自由选择的最大值之和。如果发现哪一层不对就往那棵子树的递归里再插打印逐层缩小范围。这个方法看起来糙但比单步调试快多了尤其适合算法题的日常锻炼。关于这道题我实际体会最深的一点是递归的返回值设计决定了代码的复杂度和可读性。把“偷/不偷”两种状态放进返回值里是最贴合树形结构的一种建模方式它让每个节点都成了一个独立的决策者。如果你也在学递归建议不要满足于“代码通过”而是尝试把这道题的递归展开成迭代版再对比一下两者的状态存储方式很多关于递归栈的迷惑会一下清晰起来。以后再遇到像“树上的依赖选择”这类题你会发现思路出奇地一致先找约束关系再定义状态然后让递归自己把答案带回来。