Clear Java Recursive+DP solution


  • 0
    public class Solution {
        
        Map<TreeNode, Integer> robRootMap = new HashMap<>();
        Map<TreeNode, Integer> nonRobRootMap = new HashMap<>();
        
        public int robHelper(TreeNode root, boolean robRoot) {
            if(root==null)
                return 0;
            if(robRoot && robRootMap.containsKey(root))
                return robRootMap.get(root);
            if(!robRoot && nonRobRootMap.containsKey(root))
                return nonRobRootMap.get(root);
            if(robRoot) {
                int robs = root.val+robHelper(root.left, false) + robHelper(root.right, false);
                robRootMap.put(root, robs);
                return robs;
            } else {
                int leftMax = Math.max(robHelper(root.left, false), robHelper(root.left, true));
                int rightMax = Math.max(robHelper(root.right, false), robHelper(root.right, true));
                int robs = leftMax + rightMax;
                nonRobRootMap.put(root, robs);
                return robs;
            }
        }
        
        public int rob(TreeNode root) {
            return Math.max(robHelper(root, false), robHelper(root, true));
        }
    }

Log in to reply
 

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