concise, easy, clear JAVA solution


  • 0
    M

    '''

    public int rob(TreeNode root) {
        return dfs(root, false);
    }
    
    int dfs(TreeNode t, boolean isParentRobed){
        if (t == null) return 0;
        
        
        //rob t
        int a1 = 0;
        if (!isParentRobed) a1 = t.val + dfs(t.left, true) + dfs(t.right, true);
        
        //not rob t
        int a2 = dfs(t.left, false) + dfs(t.right, false);
        
        return Math.max(a1, a2);
        
    }
    

    ''''


  • 0
    M

    Here comes the DP version.

    '''

    public int rob(TreeNode root) {
        Map<TreeNode, Integer>[] maps = new Map[2];
        for (int i=0; i<2; i++) maps[i] = new HashMap<>();
        
        return dfs(root, false, maps);
    }
    
    int dfs(TreeNode t, boolean isParentRobed, Map<TreeNode, Integer>[] maps){
        if (t == null) return 0;
        
        int idx = isParentRobed?1:0;
        if (!maps[idx].containsKey(t)){ 
        
            //rob t
            int a1 = 0;
            if (!isParentRobed) a1 = t.val + dfs(t.left, true, maps) + dfs(t.right, true, maps);
            
            //not rob t
            int a2 = dfs(t.left, false, maps) + dfs(t.right, false, maps);
            
            
            maps[idx].put(t, Math.max(a1, a2));
        }
        
        return maps[idx].get(t);
    }
    

    ''';


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.