题目

26年7月17日

func rob int {
steal,notSteal := dfs
return max
}
func dfs {
if root == nil {
return 0,0
}
leftSteal,leftNotSteal := dfs
rightSteal。rightNotSteal := dfs
curSteal := root.Val + leftNotSteal + rightNotSteal
curNotSteal:= max + max
return curSteal,curNotSteal
}

思路

这道题最先想到的思路是借鉴之前做过的“安摄像头”问题，试图用一个 flag 标记每一层是否能偷。但实际跑起来就出现了各种问题，下面把痛点拆开来讲。

痛点 1：参数传递导致状态泄漏

在第一次尝试中。我把累计金额 total 当作参数传进去：

func dfs int {
if root == nil { return total }
...
}

这样左子树和右子树共享同一个 total，导致两边相互干扰，根本无法得到正确答案。按理说，解决办法：不要把累计值作为参数。而是让递归返回自己的最大收益。

痛点 2：父节点没偷 → 子节点必偷？

我误以为“父亲没偷”就等价于“子节点一定要偷”。于是写成了：

if flag == 1 { // 父亲没有偷
total += root.Val
}

这完全忽略了子节点可以选择不偷的情况，从而导致结果偏低。真正的关系是的观点是，如果父亲没偷。子节点可以选择偷或不偷，只取两者中更大的收益；如果父亲偷了子节点一定不能偷。

痛点 3：遍历顺序错误 → 无法得到子节点信息

最初我采用的是前序遍历，想先处理当前节点再递归到子节点。不过，可此时子节点还没有计算出自己的最大收益，导致无法做出正确判断。 后序遍历才符合逻辑：先拿到左右孩子的“偷/不偷”两种结果，再决定当前是否抢劫。

痛点 4：返回值设计不当 → 代码冗余且易错

很多人只用一个返回值来存 “能否抢”，但需要同时知道两种情况的最大金额。一次性返回两个整数即可解决所有组合问题。

完整实现步骤

• #1 定义递归函数 dfs 若 node 为 nil，则返回。否则分别递归左、右子树得到 与。计算当前 “抢” 的收益：root.Val + leftSafe + rightSafe；计算当前 “不抢” 的收益：max+max。返回，
• #2 主入口 rob 调用 dfs，取两者中的最大值即为答案。说起来，
• #3 辅助函数 max

小结： 二叉树打家劫舍三要点：

• 后序遍历能先拿到下层信息。按理说，
• 双返回值直接表达“抢/不抢”。
• 不要把累计金额当成全局状态传递。怎么说呢，
• 父亲没抢并非必然让孩子必须抢。要比较两者最大值，
• 代码简洁后测试通过几乎无遗漏。

这样，你就可以轻松解决 LeetCode 337 —— 打家劫舍 III 啦！祝你刷题愉快 🚀.