树形动态规划实战：从状态定义到后序遍历解决打家劫舍III

1. 项目概述从“打家劫舍”到树形动态规划看到“打家劫舍 III”这个标题很多人的第一反应可能是“这又是个什么脑筋急转弯”。其实这是LeetCode上一个非常经典的动态规划问题也是“打家劫舍”系列的第三道题。如果说前两道题打家劫舍 I 和 II是在一维数组街道上玩“隔空取物”的游戏那么这道题直接把战场搬到了数据结构里的“二叉树”上。想象一下你是一个技术高超的“侠盗”现在要潜入一个由二叉树结构组织的社区每个节点房子里都有一定价值的财物。但社区安保系统很智能如果你偷了某个房子那么与它直接相连的父子节点房子即它的父节点和子节点的警报就会立刻被触发。你的目标是在不触发警报的前提下偷到总价值最大的财物组合。这个问题之所以经典是因为它将动态规划的核心思想——“状态定义”和“状态转移”——与树形结构的递归遍历完美结合。它考察的不仅仅是你能不能写出状态转移方程更考验你能否将树这种非线性的数据结构通过递归分解成子问题并高效地自底向上或自顶向下计算出最优解。对于准备面试尤其是国内外大厂技术面的同学来说这道题是必须啃下的硬骨头因为它综合了算法动态规划、数据结构二叉树和编程实现递归/迭代多个考点。我自己在最初刷这道题时也卡了很久。最直观的暴力搜索枚举所有可能的偷窃组合时间复杂度是指数级的完全不可行。后来理解了“后序遍历”配合“状态记录”的思路才豁然开朗。今天我就把自己踩过的坑、总结的心得以及完整的Python和C实现代码毫无保留地分享出来。无论你是刚开始接触动态规划的新手还是想巩固树形DP的老手相信这篇详细的拆解都能让你有所收获。2. 核心思路拆解为什么是树形DP要解决这个问题我们首先要彻底理解题目加在我们身上的“约束条件”不能同时偷窃相邻的节点。在二叉树中“相邻”意味着父子关系。也就是说如果你决定偷窃节点node那么你就绝对不能偷它的直接左孩子node.left、直接右孩子node.right以及它的父节点在递归中父节点的约束通过返回值向上传递来体现。2.1 暴力搜索的不可行性最朴素的想法是对于每个节点我们有两种选择偷或者不偷。那么我们可以尝试枚举整棵树所有可能的“偷窃状态组合”然后检查每种组合是否满足“不相邻”约束最后从所有合法组合中找出总价值最大的那个。这听起来简单但实现起来复杂度爆炸。一棵有N个节点的二叉树每个节点有2种状态那么理论上的状态组合就有 2^N 种。即使N只有20也有超过100万种组合需要检查这显然是不可接受的。我们需要一个更聪明的办法避免重复计算子问题——这正是动态规划DP大显身手的地方。2.2 动态规划的状态定义动态规划的精髓在于定义状态并找到状态之间的转移关系。对于树上的每一个节点我们关心的是“以这个节点为根的子树”所能获得的最大收益。但是仅仅一个“最大收益”是不够的因为这会丢失关键信息当前节点是否被偷窃这个信息会直接影响其子节点的选择。因此我们必须为每个节点定义两个状态selected或rob表示偷窃当前节点的情况下以该节点为根的子树能获得的最大收益。not_selected或not_rob表示不偷窃当前节点的情况下以该节点为根的子树能获得的最大收益。这是一个非常关键的洞见。通过为每个节点维护这两个值我们在处理父节点时就可以直接利用子节点的这两个状态值进行决策而无需关心子节点的子树内部具体是怎么偷的这完美符合动态规划的“最优子结构”性质。2.3 状态转移方程的推导现在假设我们正在处理节点node。我们已经通过递归计算出了其左孩子left_child和右孩子right_child的(selected, not_selected)状态对。情况一偷窃节点node即node.selected如果我决定偷node那么根据规则它的直接孩子left_child和right_child绝对不能被偷。因此我能从左右子树获得的收益仅限于当左右孩子“不被偷”时的最大收益。公式node.selected node.val left_child.not_selected right_child.not_selected情况二不偷窃节点node即node.not_selected如果我不偷node那么对于它的孩子left_child和right_child我就没有限制。我可以自由选择偷或不偷它们目标当然是让从左右子树获得的总收益最大化。因此对于每个孩子我取其selected和not_selected中的较大值。公式node.not_selected max(left_child.selected, left_child.not_selected) max(right_child.selected, right_child.not_selected)注意这里node.not_selected的计算是很多初学者容易混淆的地方。不偷当前节点不代表一定要偷它的子节点。最优策略是对于每个子节点我都独立地选择“偷它”或“不偷它”中能带来更大收益的那个方案然后把左右子树的最优收益加起来。子节点的选择是独立的互不影响。2.4 遍历顺序的选择为什么是后序遍历有了状态和转移方程我们需要计算整棵树每个节点的这两个状态值。应该以什么顺序遍历树呢答案是后序遍历左 - 右 - 根。原因在于我们的状态转移方程要计算节点node的selected和not_selected我们必须先知道其左右孩子left_child和right_child的对应状态值。这正是一种“自底向上”的计算过程先解决子问题子树再利用子问题的解来解决父问题当前树。后序遍历天然符合这个需求。我们递归地深入左子树计算出左子树根节点的状态对再递归深入右子树计算出右子树根节点的状态对最后回到当前节点利用左右孩子的状态对计算出当前节点的状态对。3. 代码实现详解与避坑指南理论清晰了我们来看代码实现。我会分别给出Python和C的版本并详细解释其中的关键点和容易出错的地方。3.1 Python 实现与逐行解析# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def rob(self, root: Optional[TreeNode]) - int: # 定义递归函数返回一个元组 (selected, not_selected) def dfs(node): # 递归基如果节点为空偷或不偷的收益都是0 if not node: return (0, 0) # 后序遍历先递归处理左右子树 left dfs(node.left) right dfs(node.right) # 情况1偷当前节点 # 收益 当前节点价值 不偷左子树的收益 不偷右子树的收益 selected node.val left[1] right[1] # 情况2不偷当前节点 # 收益 max(偷左子树 不偷左子树) max(偷右子树 不偷右子树) not_selected max(left[0], left[1]) max(right[0], right[1]) # 返回当前节点的状态对 return (selected, not_selected) # 从根节点开始递归最终结果是偷或不偷根节点的最大收益 result dfs(root) # 根节点也有偷或不偷两种选择取最大值 return max(result[0], result[1])代码要点与避坑指南递归函数返回值dfs函数返回一个长度为2的元组(selected, not_selected)。这是最清晰的方式。有些实现会用字典或列表但元组在Python中更轻量且意图明确。递归基Base Case空节点的处理(0, 0)必须要有。这保证了递归能够正确终止。后序遍历顺序注意left dfs(node.left)和right dfs(node.right)的调用在计算selected和not_selected之前。这是后序遍历的体现。状态转移的实现selected和not_selected的计算严格对应我们推导的公式。特别注意not_selected中对max(left[0], left[1])的调用这里left[0]对应left_selectedleft[1]对应left_not_selected。最终结果递归从根节点开始最终得到根节点的状态对。题目要求整棵树的最大收益所以我们需要取根节点被偷和根节点不被偷两种情况下的最大值即max(result[0], result[1])。一个常见的错误有人可能会想既然根节点不一定偷那是不是最终结果就是result[1]不偷根节点的收益不对。因为最优解完全有可能包含偷窃根节点的情况例如根节点价值极高而子节点价值很低。所以必须取两者最大值。3.2 C 实现与性能考量/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int rob(TreeNode* root) { // 调用递归函数返回一个pairint, int auto result dfs(root); // 取偷或不偷根节点的最大值 return max(result.first, result.second); } private: // 返回 pair偷当前节点的最大收益 不偷当前节点的最大收益 pairint, int dfs(TreeNode* node) { if (node nullptr) { return {0, 0}; // 空节点收益均为0 } // 后序遍历 auto left dfs(node-left); auto right dfs(node-right); // 偷当前节点 int selected node-val left.second right.second; // 不偷当前节点 int not_selected max(left.first, left.second) max(right.first, right.second); return {selected, not_selected}; } };C实现特点与注意事项使用std::pairC标准库中的pairint, int非常适合用来返回两个状态值语义清晰。也可以自己定义结构体但pair更简洁。使用auto关键字auto left dfs(node-left);让代码更简洁编译器会自动推导出left的类型是pairint, int。访问成员通过first和second来访问pair的两个元素对应selected和not_selected。递归基同样对空指针返回{0, 0}。性能这个算法的时间复杂度是 O(N)其中 N 是树中的节点数因为每个节点只被访问一次。空间复杂度主要取决于递归调用栈的深度在最坏情况树退化成链表下是 O(N)平均情况平衡树下是 O(log N)。对于LeetCode的约束这个复杂度是完全可接受的。实操心得在C中注意递归深度。虽然题目中树的节点数范围通常不会导致栈溢出但在处理特别深或不平衡的树时心里要有这根弦。理论上可以将递归改为显式栈的迭代后序遍历来实现以避免潜在的栈溢出风险但代码会复杂很多。在面试中先给出清晰正确的递归解法通常是更优选择。4. 算法深入分析与复杂度证明4.1 时间复杂度O(N) 的必然性我们声称算法的时间复杂度是 O(N)N 为节点数。为什么 我们的dfs函数对树进行了一次后序遍历。在遍历过程中每个节点恰好被访问一次。在访问每个节点时我们只进行了常数时间的操作从左右子节点的返回值中取出两个值进行两次加法、两次max比较以及一次构造返回值的操作。 因此总时间与节点数 N 成线性关系即 O(N)。4.2 空间复杂度递归深度的代价空间复杂度分为两部分递归调用栈空间这取决于树的高度 H。在最坏情况下树退化成一条链例如每个节点都只有左孩子此时树高 H N递归深度为 N空间复杂度为 O(N)。在最好情况下树是完全平衡的高度 H ≈ log₂N空间复杂度为 O(log N)。算法本身使用的额外空间除了递归栈我们只使用了几个局部变量left,right,selected,not_selected这些是常数空间 O(1)。因此总的空间复杂度是 O(H)在最坏情况下为 O(N)。4.3 与记忆化搜索Memoization的对比有同学可能会问这看起来像递归为什么说是动态规划它和“记忆化搜索”有什么区别 实际上我们采用的正是记忆化搜索形式的动态规划也称为“自顶向下的DP”。记忆化搜索在递归过程中如果遇到重复子问题就将结果保存下来记忆下次直接查表返回避免重复计算。我们这里的实现仔细看对于树中的每个节点我们的dfs函数只会被调用一次。为什么因为每个节点作为其自身子树的根这个“子问题”是唯一的。我们从根节点开始递归地分解问题每个子问题子树只解决一次其结果通过返回值传递给父问题。这本质上已经避免了重复计算虽然没有显式地用一个memo字典来存储但递归函数的调用栈和返回值传递机制隐式地保证了这一点。所以这是一种非常高效且自然的树形DP实现方式。如果要显式写成记忆化搜索可以这样Python示例class Solution: def rob(self, root): memo {} def dfs(node): if not node: return (0, 0) if node in memo: # 如果该节点的状态已计算过直接返回 return memo[node] left dfs(node.left) right dfs(node.right) selected node.val left[1] right[1] not_selected max(left[0], left[1]) max(right[0], right[1]) memo[node] (selected, not_selected) return memo[node] result dfs(root) return max(result[0], result[1])对于树结构显式记忆化的收益不大因为每个节点天然只被访问一次。但在图等可能重复访问同一状态的问题中记忆化就至关重要。5. 变种问题与扩展思考理解了“打家劫舍 III”的核心我们可以看看它的几个变种和扩展这能帮你更好地掌握这类树形DP问题的精髓。5.1 如果房子不是二叉树而是多叉树假设社区结构是一棵普通的树每个节点可能有多个孩子规则不变。我们的解法只需要做微调。 状态定义不变每个节点仍然需要(selected, not_selected)两个状态。 状态转移方程需要稍作修改node.selected node.val sum(child.not_selected for child in node.children)node.not_selected sum(max(dfs(child)[0], dfs(child)[1]) for child in node.children)遍历顺序依然是后序遍历先处理所有孩子再处理当前节点。代码实现上将处理左右孩子的循环改为处理所有孩子的循环即可。5.2 如果警报条件变化隔两层才触发原题是偷了节点其父子节点不能偷。如果规则变成“偷了节点其父节点和子节点不能偷但孙子节点可以偷”即相隔一层即可问题会变得更复杂。 此时一个节点的状态不仅受其孩子影响还受其孙子影响。状态定义可能需要扩展。一种思路是定义三个状态selected: 偷当前节点。not_selected_but_child_selected: 不偷当前节点但偷了至少一个直接子节点。not_selected_and_child_not_selected: 不偷当前节点且所有直接子节点也都没偷。 然后推导这三个状态之间的转移方程。这显然比原题复杂但核心思想依然是定义足够的状态来捕获决策对后续选择的影响。5.3 如何输出具体偷窃了哪些节点原题只要求返回最大金额。如果面试官追问“请输出偷窃了哪些节点”这就是一个经典的“DP方案回溯”问题。 我们的DP过程记录了每个节点在“偷”与“不偷”状态下的最优收益。要回溯方案我们需要从根节点开始根据最终的选择是selected收益大还是not_selected收益大以及子节点的状态决定当前节点是否被偷然后递归地决定子节点的选择。回溯步骤简述Python思路修改dfs函数让它除了返回收益还返回能达到该收益的节点选择列表或一个标记。或者更常见的做法是先运行一遍DP计算出所有节点的selected和not_selected值。然后写一个独立的backtrack函数从根节点开始比较root.selected和root.not_selected。如果root.selected更大说明最优方案中偷了根节点。将根节点加入结果列表然后递归地处理root.left和root.right但必须强制它们处于“不被偷”的状态即接下来只看它们的not_selected分支。如果root.not_selected更大说明最优方案中没偷根节点。那么对于每个孩子我们选择能带来更大收益的那个状态可能是偷也可能是不偷然后递归处理。注意可能存在多个最优方案收益相同但节点组合不同回溯时需要处理。6. 常见错误与调试技巧在实际编写和调试代码时以下几个错误非常常见错误1状态转移方程写反# 错误示例 selected node.val max(left[0], left[1]) max(right[0], right[1]) # 错偷了node就不能偷孩子。 not_selected left[1] right[1] # 错不偷node孩子可以偷也可以不偷。诊断用一个小树如只有两三层手动模拟或者用LeetCode的测试用例例如[3,2,3,null,3,null,1]跑一下结果肯定不对。仔细对照我们推导的公式检查。错误2忘记处理空节点递归函数没有if not node: return (0, 0)这一句那么在遍历到叶子节点的空孩子时就会报错尝试访问None.val或None.left。错误3最终结果只返回了not_selectedreturn result[1] # 错误可能最优解需要偷根节点。诊断用一个简单的例子测试比如树只有一个节点[100]。正确结果应该是100偷这个节点。如果你的程序返回0那就是犯了这个问题。错误4C中未考虑负数节点值题目描述中node.val是整数但并未说明是非负。我们的状态转移方程中使用了max函数它同样适用于负数选择较大的收益。但如果题目明确说明财物价值为非负整数那么我们可以利用这一点进行一些优化例如not_selected一定大于等于0但基本算法不变。调试技巧画图拿一张纸画一棵简单的二叉树3-5个节点手动模拟算法的递归过程为每个节点算出(selected, not_selected)。这是理解算法最有效的方式。打印日志在递归函数入口和返回处打印节点值和返回的状态对观察计算顺序和结果。def dfs(node): if not node: print(fNode: None - (0, 0)) return (0, 0) print(fEntering node: {node.val}) left dfs(node.left) right dfs(node.right) selected node.val left[1] right[1] not_selected max(left[0], left[1]) max(right[0], right[1]) print(fLeaving node: {node.val} - ({selected}, {not_selected})) return (selected, not_selected)使用LeetCode的测试用例LeetCode提供的示例和测试用例覆盖了各种边界情况空树、单节点、左斜树、右斜树、普通树。逐个测试确保都能通过。7. 总结与个人心得“打家劫舍 III”是一道质量极高的题目它不像一些纯技巧性的题目那样刁钻而是扎实地考察了对动态规划和树形数据结构的理解。通过这道题我们可以深刻体会到“状态定义”在DP中的核心地位。定义出(selected, not_selected)这个状态对问题就解决了一大半。我个人在反复练习这道题和类似题目如“二叉树中的最大路径和”后总结出一个树形DP的通用思路框架确定状态站在一个节点的角度思考解决以它为根的子树问题需要哪些信息这些信息往往需要包含“当前节点处于某种情况”下的结果。像本题就需要知道“偷它”和“不偷它”两种情况下的最优解。定义递归函数设计一个递归函数输入一个节点返回我们需要的信息通常是一个值或一个结构体/元组。推导转移方程思考如何利用子节点的返回信息计算出当前节点的信息。这是最核心的一步需要仔细分析约束条件。确定遍历顺序绝大多数树形DP都采用后序遍历因为需要先知道子问题的解才能解决父问题。处理递归基明确空节点或叶子节点的返回结果。获取最终答案从根节点的递归返回值中提取或计算出整个问题的答案。最后再分享一个面试小技巧当面试官问出这道题时在写出代码之前最好先清晰地阐述你的状态定义和状态转移方程并说明为什么选择后序遍历。这能展示你清晰的思维过程比直接闷头写代码要加分得多。写完代码后主动分析时间复杂度和空间复杂度并提及可能的变种如输出偷窃路径更能体现你的技术深度。