vvrf / DSA.log

问题拆解

房子排成一棵二叉树，直接相连的父子不能同时偷，求最大金额。线性版打家劫舍沿数组从左往右递推，这里“下一间房”变成了“两个孩子”，递推自然改沿着树自底向上做。

一个诱人但错误的贪心是“隔层偷”：偷第 1、3、5 层或第 2、4 层，取大者。反例很好构造——某条路径上最优解可以连跳两层（偷爷爷和孙子的孙子），层的奇偶性并不能刻画约束。约束只发生在相邻的父子之间，所以状态也应该建在节点上：对每个节点区分“偷它”与“不偷它”两种情形下，其子树能得到的最大金额。

孩子只上报一个“子树最优值”是不够的：这个最优值可能建立在“偷了孩子自己”的前提上，而父节点一旦想偷自己，就需要孩子“不被偷”时的最优值。信息不全，父节点就无法决策——所以每个节点必须把（偷, 不偷）两个值都传上去，让父节点做选择。

转移只有两条：偷当前节点，则两个孩子都不能偷，rob = node.val + left.notRob + right.notRob；不偷当前节点，则每个孩子独立地取自己两种状态的较大者，notRob = max(left) + max(right)。注意后者不是强制偷孩子——不偷父亲不等于必须偷孩子，漏掉这层理解会把 notRob 错写成 left.rob + right.rob。

后序遍历上传二元组

后序遍历保证算某个节点时左右孩子的二元组已经就绪，空节点返回 (0, 0) 作为递归基。

public int rob(TreeNode root) {
    int[] res = dfs(root);
    return Math.max(res[0], res[1]);
}

// 返回 [偷当前节点的最大值, 不偷当前节点的最大值]
private int[] dfs(TreeNode node) {
    if (node == null) return new int[]{0, 0};
    int[] left = dfs(node.left);
    int[] right = dfs(node.right);
    int rob = node.val + left[1] + right[1]; // 偷它，孩子都不能偷
    int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); // 不偷它，孩子随意
    return new int[]{rob, notRob};
}

def rob(root) -> int:
    # 返回 (偷当前节点的最大值, 不偷当前节点的最大值)
    def dfs(node):
        if node is None:
            return 0, 0
        left = dfs(node.left)
        right = dfs(node.right)
        rob = node.val + left[1] + right[1]  # 偷它，孩子都不能偷
        not_rob = max(left) + max(right)  # 不偷它，孩子随意
        return rob, not_rob

    return max(dfs(root))

func rob(root *TreeNode) int {
    rob, notRob := dfs(root)
    return max(rob, notRob)
}

// 返回 (偷当前节点的最大值, 不偷当前节点的最大值)
func dfs(node *TreeNode) (int, int) {
    if node == nil {
        return 0, 0
    }
    lRob, lNot := dfs(node.Left)
    rRob, rNot := dfs(node.Right)
    rob := node.Val + lNot + rNot          // 偷它，孩子都不能偷
    notRob := max(lRob, lNot) + max(rRob, rNot) // 不偷它，孩子随意
    return rob, notRob
}

use std::rc::Rc;
use std::cell::RefCell;

pub fn rob(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    // 返回 (偷当前节点的最大值, 不偷当前节点的最大值)
    fn dfs(node: &Option<Rc<RefCell<TreeNode>>>) -> (i32, i32) {
        match node {
            None => (0, 0),
            Some(n) => {
                let n = n.borrow();
                let (l_rob, l_not) = dfs(&n.left);
                let (r_rob, r_not) = dfs(&n.right);
                let rob = n.val + l_not + r_not; // 偷它，孩子都不能偷
                let not_rob = l_rob.max(l_not) + r_rob.max(r_not); // 不偷它，孩子随意
                (rob, not_rob)
            }
        }
    }
    let (rob, not_rob) = dfs(&root);
    rob.max(not_rob)
}

这套写法还悄悄解决了“重复子问题”：如果按朴素定义写 rob(root) = root.val + rob(四个孙子) vs rob(两个孩子)，孙子的子树会在两条分支里被反复计算，需要额外挂一个记忆化哈希表。而二元组版本每个节点恰好被访问一次，状态就地传递，无需任何缓存——把“选/不选”显式编码进返回值，是比记忆化更干净的解法。根节点没有父亲约束，最终答案取两个状态的较大者。

复杂度

指标	复杂度	原因
时间	`O(n)`	每个节点恰好访问一次，转移是常数次比较和加法
空间	`O(h)`	递归栈深度为树高，最坏（链状树）退化为 O(n)

可以迁移的模式

树形 DP 的标准姿势：后序遍历，孩子先算，节点把本层的所有状态打包上传；
上传什么由父节点的决策需求决定——父节点用得着的状态一个都不能少；
“不选当前”不等于“必选孩子”，每个孩子仍独立取两态较大者。

同样的“节点返回状态元组”还能解树的直径、二叉树最大路径和、监控二叉树（三状态版），是处理树上约束问题的通用框架。