[337. House Robber III] #leetcode

337_0823.java

class Solution {
    // O(n^2) O(n)
    public int rob(TreeNode root) {
        return dfs(root, false);
    }
    public int dfs(TreeNode node, Boolean robbed) {
        if ( node == null ) return 0;
        
        int rob_node = 0, not_rob_node = 0;
        if (robbed) {
            not_rob_node = dfs(node.left, false) + dfs(node.right, false);
        } else {
            rob_node = dfs(node.left, true) + dfs(node.right, true) + node.val;
            not_rob_node = dfs(node.left, false) + dfs(node.right, false);
        }
        
        return Math.max(rob_node, not_rob_node);
    }
}

class Solution2 {
    // O(n) O(n)
    private Map<TreeNode, Integer> map = new HashMap<>();
    public int rob(TreeNode root) {
        return dfs(root);
    }
    public int dfs(TreeNode node) {
        if ( node == null ) return 0;
        if ( map.containsKey(node) ) return map.get(node);
        
        int val = 0;
        if (node.left != null) {
            val += dfs(node.left.left) + dfs(node.left.right);
        } 
        if (node.right != null) {
            val += dfs(node.right.left) + dfs(node.right.right);
        }
        
        val = Math.max(val + node.val, dfs(node.left) + dfs(node.right));
        
        map.put(node, val);
        return val;
    }
}

class Solution3 {
    // O(n) O(1)
    public int rob(TreeNode root) {
        int[] res = dfs(root);
        return Math.max(res[0], res[1]);
    }
    
    public int[] dfs(TreeNode node) {
        if ( node == null ) return new int[] {0, 0};
        
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        
        int[] res = new int[2];
        
        // not rob node
        res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        // rob node
        res[1] = node.val + left[0] + right[0];
            
        return res;
    }
}