337. 打家劫舍 III(leetcode) 2

https://leetcode.cn/problems/house-robber-iii/description/

此前做过此题,不过时隔一年再做一遍有新的理解

class Solution {

    private Map<TreeNode,Integer> vis = new HashMap<>();

    public int rob(TreeNode root) {
        // 在二叉树上做选择,不能选择直接相连的节点
        // f[i] 表示以 i 为根的树中能获取到的最大金额,集合法表示以i为根的树中的所有可能的走法,属性为最大价值
        // 从子树考虑一直推导到根节点
        // 以节点i是否偷取作为标准,也可划分子集
        // 偷i: 那么i的子节点都不能偷,只能偷i的孙子节点,节点编号为i/2/2=i/4
        // f[i]=max(f[i/4],f[i/4+1],f[i/4+2],f[i/4+3]) + nums[i],i/4>=0
        // 不偷i: 那么i1的子节点可以偷, f[i] = f[i/2]+f[i/2+1]
        //
        // 转化成树形dp做法:使用搜索dfs或者bfs,dfs递归需要定义函数意义
        // dfs(root)表示以root为根的树能获取到的最大金额
        // 不偷: dfs(root) = dfs(root.left) + dfs(root.right)
        // 偷 dfs(root) = root.val + dfs(root.left.left) + dfs(root.left.right) + dfs(root.right.left) + dfs(root.right.right)
        // 边界条件: if(root==null), return 0,为叶子结点时返回值
        // 无左右儿子,直接返回当前节点值
        return dfs(root);
    }

    int dfs(TreeNode root) {
        // 后续遍历
        if (root == null) return 0;
        if (root.left == null && root.right == null) return root.val;
        // 剪枝
        if (vis.get(root) != null) return vis.get(root);
        // 不偷root
        int left = dfs(root.left);
        int right = dfs(root.right);
        // 偷root
        int steal=root.val;
        if (root.left != null) {
            steal +=  dfs(root.left.left) + dfs(root.left.right);
        }
        if (root.right != null) {
            steal += dfs(root.right.left) + dfs(root.right.right);
        }
        int res = Math.max(left+right, steal);
        // 运行到此处时,意味着当前节点结果计算完毕,可以保存已计算的结果进行剪枝
        vis.put(root,res);
        return res;
    }
}