题目描述
二叉树每个节点是一户，不能同时偷父子节点，求最大金额。
root = [3,2,3,null,3,null,1]
输出 = 7
思路解析
关键不是背模板，而是看懂为什么这题适合树形 DP。
1. 后序遍历，先算左右孩子：后序遍历，先算左右孩子
2. 叶子节点：叶子节点：偷=值，不偷=0
3. 如果偷当前节点，就不能偷孩子：如果偷当前节点，就不能偷孩子
4. 偷当前 = node.val + 左不偷 + 右不偷：偷当前 = node.val + 左不偷 + 右不偷
5. 如果不偷当前，孩子可偷可不偷取最大：如果不偷当前，孩子可偷可不偷取最大
6. 不偷当前 = max(左) + max(右)：不偷当前 = max(左) + max(右)
7. 根节点也返回偷/不偷两种：根节点也返回偷/不偷两种
8. 答案取根的最大值：答案取根的最大值
把这句话记住，下次遇到同类题，就能更快选出方向。
用一个小问题检查自己是不是真的懂了。
参考代码（Python）
Python
1class Solution:
2 def rob(self, root):
3 def dfs(node):
4 if not node:
5 return (0, 0)
6 l0, l1 = dfs(node.left)
7 r0, r1 = dfs(node.right)
8 rob_it = node.val + l0 + r0
9 skip_it = max(l0, l1) + max(r0, r1)
10 return (skip_it, rob_it)
11 return max(dfs(root))复杂度分析
- 时间复杂度：O(n) —— 每个核心状态按算法要求处理固定次数
- 空间复杂度：O(h) —— 只保存必要的辅助结构或递归栈
套路模板
模板不是死背，而是提醒你写代码前先把状态、转移和边界排好。
Python
1# 树形 DP 通用检查表
2# 1. 定义状态/指针/容器
3# 2. 每轮只做一个清晰动作
4# 3. 更新答案并处理边界易错点
- 错误写法：只按层奇偶来偷 → 正确写法：每棵子树都要返回偷/不偷两种状态（局部结构不一定按层最优）
- 错误写法：只按样例推代码 → 正确写法：先写清状态含义和边界条件（样例太少，隐藏用例专打边界）
- 错误写法：变量名和动画不一致 → 正确写法：代码变量沿用动画里的核心名字（学习时最怕脑内维护两套概念）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。