[!info] related notes 动态规划 打家劫舍 二叉树基础 树形 DP

打家劫舍 III

题目链接：https://leetcode.cn/problems/house-robber-iii/

为什么是树形 DP

每个节点都面临两种状态：

• 偷当前节点
• 不偷当前节点

并且选择会影响左右孩子是否能偷。

状态设计

对每个节点返回一个长度为 2 的数组：

• res[0]：在当前节点整棵子树内、不偷当前节点时的最大收益
• res[1]：在当前节点整棵子树内、偷当前节点时的最大收益

转移

• 不偷当前节点：左右子树都可以偷也可以不偷，取各自最大值
• 偷当前节点：左右孩子都不能偷

JavaScript

var rob = function(root) {
    function dfs(node) {
        if (!node) return [0, 0];

        const left = dfs(node.left);
        const right = dfs(node.right);

        const notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        const robNode = node.val + left[0] + right[0];

        return [notRob, robNode];
    }

    const res = dfs(root);
    return Math.max(res[0], res[1]);
};

每个节点访问一次，时间 O(n)，递归栈 O(h)。退化成链时 h = n，JavaScript 递归实现可能超过调用栈限制；可改用显式栈做后序遍历。