好的，我们这次来详细讲解 LeetCode 第 337 题「打家劫舍 III」。

题目描述

在上次打劫完一条街道（「打家劫舍 I」）和一圈房屋（「打家劫舍 II」）后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父”房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。

如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1：

输入: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7。

示例 2：

输入: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9。

解题思路

这个问题是「打家劫舍」系列在二叉树结构上的扩展。核心约束是：不能同时偷窃直接相连的两个节点（即父子节点不能同时被偷）。

第一步：分析问题结构

对于二叉树中的任意一个节点 node，小偷面对两种选择：

1. 偷窃当前节点：那么就不能偷窃它的左右子节点，但可以偷窃子节点的子树（跳过子节点）。
2. 不偷窃当前节点：那么可以偷窃它的左右子节点（以及子节点的子树）。

因此，对于每个节点，我们需要知道两种情况下的最大收益：

• rob(node)：偷窃以 node 为根的子树能获得的最大收益（可以偷 node，也可以不偷，取最大值）。
• 但更精细的做法是，我们为每个节点返回一个长度为 2 的数组 [a, b]：
  • a 表示偷窃当前节点的情况下，子树的最大收益。
  • b 表示不偷窃当前节点的情况下，子树的最大收益。

第二步：定义状态转移

设 res = [a, b] 为节点 node 的返回结果：

• 如果偷 node，则不能偷左右子节点，所以：

  a = node.val + left[1] + right[1]
  

  其中 left[1] 表示不偷左子节点时的最大收益，right[1] 同理。
• 如果不偷 node，那么可以偷左右子节点，也可以不偷，取最大值：

  b = max(left[0], left[1]) + max(right[0], right[1])
  

  因为对于每个子节点，我们可以自由选择偷或不偷，取收益大的情况。

第三步：递归基（终止条件）

如果节点 node 为空，那么偷或不偷的收益都是 0，返回 [0, 0]。

第四步：递归过程

采用后序遍历（左右根）：

1. 递归计算左子树的 [left_rob, left_not_rob]。
2. 递归计算右子树的 [right_rob, right_not_rob]。
3. 计算当前节点的 a 和 b：

   a = node.val + left_not_rob + right_not_rob
   b = max(left_rob, left_not_rob) + max(right_rob, right_not_rob)
   

4. 返回 [a, b]。

第五步：最终结果

从根节点开始递归，最终返回 max(a, b)，即偷或不偷根节点的最大收益。

举例说明（以示例 1 为例）

二叉树：

     3
    / \
   2   3
    \   \ 
     3   1

后序遍历：

1. 节点 2（左子节点）：

   • 左子节点为空 → left = [0,0]
   • 右子节点为 3：
     • 左右子节点都为空 → 返回 [3, 0]
   • 对于节点 2：
     • 偷：2 + 0 + 0 = 2
     • 不偷：max(0,0) + max(3,0) = 0 + 3 = 3
     • 返回 [2, 3]

2. 节点 3（右子节点）：

   • 左子节点为空 → left = [0,0]
   • 右子节点为 1：
     • 左右子节点都为空 → 返回 [1, 0]
   • 对于节点 3：
     • 偷：3 + 0 + 0 = 3
     • 不偷：max(0,0) + max(1,0) = 0 + 1 = 1
     • 返回 [3, 1]

3. 根节点 3：

   • 左子节点返回 [2, 3]
   • 右子节点返回 [3, 1]
   • 偷根节点：3 + 3 + 1 = 7（不能偷左右子节点，所以用它们的 b 值）
   • 不偷根节点：max(2,3) + max(3,1) = 3 + 3 = 6
   • 返回 [7, 6]

最终结果：max(7, 6) = 7，与示例一致。

代码实现（Python）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node:
                return (0, 0)  # (偷当前节点的最大收益, 不偷当前节点的最大收益)
            left = dfs(node.left)
            right = dfs(node.right)
            # 偷当前节点，则不能偷左右子节点
            rob_curr = node.val + left[1] + right[1]
            # 不偷当前节点，则可偷或不偷左右子节点，取最大值
            not_rob_curr = max(left[0], left[1]) + max(right[0], right[1])
            return (rob_curr, not_rob_curr)
        
        res = dfs(root)
        return max(res[0], res[1])

复杂度分析

• 时间复杂度：O(n)，每个节点访问一次。
• 空间复杂度：O(h)，递归栈空间，h 为树高。

总结

本题的关键在于为每个节点返回两种状态的最优解，通过后序遍历自底向上计算，避免重复计算（类似动态规划）。这种方法既保证了正确性，又具有较高的效率。