打家劫舍 III - Stellar Observer Protocol

626 字

3 分钟

打家劫舍 III

2025-08-20

Algorithms

树

/

深度优先搜索

/

动态规划

/

二叉树

题目描述#

称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额。

解题思路#

树形DP框架：
- 采用后序遍历（左右根）处理二叉树节点
- 每个节点返回[偷, 不偷]两种状态的最大收益
状态转移方程：
- 选择偷当前节点：收益 = 当前值 + 左右子树不偷的收益
- 选择不偷当前节点：收益 = max(左子树偷/不偷) + max(右子树偷/不偷)
递归终止条件：
- 空节点返回[0, 0]
结果提取：
- 根节点返回值的最大值即为最终解### 关键洞察

关键洞察#

状态分离原理：
- 每个节点独立维护偷与不偷的最优解
- 避免全局变量存储状态
决策独立性：
- 偷当前节点强制跳过直接子节点
- 不偷当前节点自由选择子孙方案
最优子结构：
- 父节点最优解依赖子节点最优解
- 符合动态规划特性
空间共享优化：
- 递归栈复用计算结果
- 无需额外存储中间状态

复杂度分析#

指标	说明
时间复杂度	O(n)：每个节点访问1次
空间复杂度	O(h)：递归栈深度（h为树高度）

代码实现#

1
/**
2
 * Definition for a binary tree node.
3
 * function TreeNode(val, left, right) {
4
 *     this.val = (val===undefined ? 0 : val)
5
 *     this.left = (left===undefined ? null : left)
6
 *     this.right = (right===undefined ? null : right)
7
 * }
8
 */
9
/**
10
 * @param {TreeNode} root
11
 * @return {number}
12
 */
13
var rob = function(root) {
14
    const dfs = (node) =>{
15
        if(node === null){
16
            return [0,0];
17
        }
18
        const l = dfs(node.left);
19
        const r = dfs(node.right);
20
        const selected = node.val + l[1] + r[1];
21
        const noSelected = Math.max(l[0],l[1]) + Math.max(r[0],r[1]);
22
        return [selected,noSelected];
23
    }
24
    const rootStatus = dfs(root);
25
    return Math.max(...rootStatus);
26
};