337. 打家劫舍 III (opens new window)

1.树形dp

每个节点都有两种搜索状态，抢或者是不抢，因此用两个哈希表分别保存当前节点在两种状态下的最大金额。要注意，树的dfs最好一个节点只搜索一次，否则因为树形结构容易导致时间复杂度呈指数级别增长。

第一版

😭😭😭超时。函数返回当前节点在pos状态下的最大金币数量。这里要明白为什么会超时，主要在于pos==0时的写法，虽然明面上每个节点仅仅访问了两次，时间复杂度与标答相比也没差多少，实则不然。因为每个节点都会搜索使用和不使用两种情况，所以到孙子节点同一个状态会搜索两次，再往下就是指数级别的时间复杂度。

class Solution {
    int res=0;
    public int rob(TreeNode root) {
        return Math.max(dfs(root,-1),dfs(root,1));
    }
    public int dfs(TreeNode root,int pos){
        if(root==null) return 0;
        int temp=0;
        if(pos==1){
            temp+=root.val;
            int left=root.left==null?0:dfs(root.left,-1);
            int right=root.right==null?0:dfs(root.right,-1);
            temp+=left+right;
        }
        else{
            int left=root.left==null?0:Math.max(dfs(root.left,-1),dfs(root.left,1));
            int right=root.right==null?0:Math.max(dfs(root.right,-1),dfs(root.right,1));
            temp+=left+right;
        }
        return temp;
    }
}

改进

class Solution {
    Map<TreeNode, Integer> used = new HashMap<>();
    Map<TreeNode, Integer> notused = new HashMap<>();

    public int rob(TreeNode root) {
        dfs(root);
        return Math.max(used.getOrDefault(root, 0), notused.getOrDefault(root, 0));
    }

    public void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.left);
        dfs(root.right);
        used.put(root, root.val + notused.getOrDefault(root.left, 0) + notused.getOrDefault(root.right, 0));
        notused.put(root, Math.max(notused.getOrDefault(root.left, 0), used.getOrDefault(root.left, 0)) + Math.max(notused.getOrDefault(root.right, 0), used.getOrDefault(root.right, 0)));
    }
}

2.后序遍历

• 后续遍历：因为遍历过程中需要计算到达当前节点的路径和。因此如果自顶向下计算时，每一个子节点的路径和都会重复加上根节点的val。
• 每个节点根据子节点的结果计算出选或不选两个状态下的金额数。同时这里返回的金额指的是子树能够偷窃的最大金额。

class Solution {
    public int rob(TreeNode root) {
        int[] res=dfs(root);
        return Math.max(res[0],res[1]);
    }
    public int[] dfs(TreeNode root){
        int[] left=new int[]{0,0};
        int[] right=new int[]{0,0};
        if(root.left!=null) left=dfs(root.left);
        if(root.right!=null) right=dfs(root.right);
        int choose=left[0]+right[0]+root.val;
        int noChoose=Math.max(left[0],left[1])+Math.max(right[0],right[1]);
        return new int[]{noChoose,choose};
    }
}