思路

不会做，告辞。

树形DP

说起来逻辑还是很好理解的
dp的长度只有2 ！含义就是 这个节点 [偷，不偷]的最大金额
然后递归做
当前节点不偷，那么金钱=左子点[偷，不偷]最大值 + 右子点[偷，不偷]最大值
当前节点偷，那么金钱 =当前节点钱+左右子点都不偷
DP来做，看代码

var rob = function(root) {
    const robOrder =function(node){
        // 递归出口
        if (!node) return [0, 0];
        const left =robOrder(node.left)
        const right =robOrder(node.right)
        // 不偷当前节点，左右子节点都可以偷或不偷，取最大值
        const Donot =Math.max(left[0],left[1])+Math.max(right[1],right[0])
        // 偷当前节点，左右子节点只能不偷
        const Do =node.val +left[0] +right[0]
        // [不偷，偷]
        return [Donot, Do]
    };
    const res =robOrder(root)
    console.log(res)
    return Math.max(...res)
};

最基本的递归法

var rob = function (root) {
    if (root == null) return 0;

    let val1 = root.val; //偷当前节点 并且偷其左右孙子
    if (root.left) val1 += rob(root.left.left) + rob(root.left.right);
    if (root.right) val1 += rob(root.right.left) + rob(root.right.right);

    let val2 = rob(root.left) + rob(root.right); // 不偷当前节点 偷其左右孩子

    return Math.max(val1, val2);
};

超时

记忆化递归

let rob = root => {
    let map = new Map();
    let inner = (root) => {
        if (!root) return 0;
        if (map.has(root)) return map.get(root); // 记忆化，之前存在过 直接返回无须进行重复计算

        let val1 = root.val; //偷当前节点 并且偷其左右孙子
        if (root.left) val1 += inner(root.left.left) + inner(root.left.right);
        if (root.right) val1 += inner(root.right.left) + inner(root.right.right);

        let val2 = inner(root.left) + inner(root.right); // 不偷当前节点 偷其左右孩子

        let res = Math.max(val1, val2);
        map.set(root, res);
        return res;
    }
    return inner(root);
}