我来给你讲解 LeetCode 第 337 题「打家劫舍 III」。

题目描述

小偷发现了一个新的地区，这个地区的房屋排列形式是一棵二叉树。每个房屋只有一个“父”房屋与之相连，且所有房屋形成一棵二叉树。如果两个直接相连的房屋在同一晚被闯入，系统会自动报警。

给定一个二叉树的根节点 root，每个节点对应一个房屋，节点值表示房屋内的金额。计算在不触发警报的情况下，小偷一晚上能够盗取的最高金额。

解题思路

第一步：理解问题约束

• 不能同时偷直接相连的两个节点（即父子节点不能同时被偷）
• 需要最大化偷取的总金额
• 房屋排列是二叉树结构

第二步：分析问题特性

对于任意一个节点，有两种选择：

1. 偷当前节点：那么不能偷它的左右子节点，但可以偷子节点的子节点
2. 不偷当前节点：那么可以偷它的左右子节点

这自然引导我们使用递归或动态规划的思路。

第三步：设计递归函数

我们可以为每个节点定义一个状态数组 [偷, 不偷]：

• 偷：选择偷当前节点时，以当前节点为根的子树能获得的最大金额
• 不偷：选择不偷当前节点时，以当前节点为根的子树能获得的最大金额

递归函数可以返回这个二元组。

第四步：推导状态转移方程

对于节点 node：

1. 如果偷当前节点：
   • 金额 = node.val + 左子树不偷的最大金额 + 右子树不偷的最大金额
2. 如果不偷当前节点：
   • 金额 = max(左子树偷, 左子树不偷) + max(右子树偷, 右子树不偷)

用公式表示：

偷 = node.val + left[不偷] + right[不偷]
不偷 = max(left[偷], left[不偷]) + max(right[偷], right[不偷])

第五步：实现递归解法（带记忆化）

def rob(root):
    def dfs(node):
        if not node:
            return [0, 0]  # [偷, 不偷]
        
        left = dfs(node.left)
        right = dfs(node.right)
        
        # 偷当前节点
        rob_current = node.val + left[1] + right[1]
        # 不偷当前节点
        skip_current = max(left[0], left[1]) + max(right[0], right[1])
        
        return [rob_current, skip_current]
    
    result = dfs(root)
    return max(result[0], result[1])

第六步：算法复杂度分析

• 时间复杂度：O(n)，每个节点只访问一次
• 空间复杂度：O(h)，其中 h 是树的高度，主要是递归栈的空间

第七步：举例验证

考虑二叉树：

     3
    / \
   2   3
    \   \ 
     3   1

计算过程：

1. 叶子节点 3（值为3）：[3, 0]
2. 叶子节点 1：[1, 0]
3. 节点 2：左子树为空 [0,0]，右子树 [3,0] → [2+0=2, max(0,0)+max(3,0)=3] = [2, 3]
4. 节点 3（右）：左子树为空，右子树 [1,0] → [3+0=3, max(0,0)+max(1,0)=1] = [3, 1]
5. 根节点 3：左子树 [2,3]，右子树 [3,1] → [3+3+1=7, max(2,3)+max(3,1)=3+3=6] = [7, 6]

最终结果：max(7, 6) = 7

第八步：算法优化说明

这种解法已经是优化后的方案，通过后序遍历（左右根）确保每个子问题只计算一次，避免了重复计算。相比暴力递归的指数复杂度，这种动态规划方法将复杂度降到了线性。

这个解法巧妙地利用了树形结构的特点，将问题分解为子问题，是树形动态规划的经典应用。