My Simple and Clear Java Solution With Using Memoization


  • 0
    K
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        
        HashMap<Set, Integer> dp = new HashMap<Set, Integer>();
        
        public int rob(TreeNode root) {
            return order(root, false);
        }
        
        private int order(TreeNode root, boolean didRobPrev) {
            if (root == null) {
                return 0;
            }
        
            Set set = new Set(root, didRobPrev);
            if (dp.containsKey(set)) {
                return dp.get(set);
            }
        
            if (didRobPrev) {
                int sum = 0;
                sum += order(root.left, false);
                sum += order(root.right, false);
                dp.put(set, sum);
                return sum;
            } else {
                int sum1 = root.val;
                sum1 += order(root.left, true);
                sum1 += order(root.right, true);
                
                int sum2 = 0;
                sum2 += order(root.left, false);
                sum2 += order(root.right, false);
                int maxSum = Math.max(sum1, sum2);
                dp.put(set, maxSum);
                return maxSum;
            }
        }
        
        class Set {
            
            TreeNode node;
            boolean didRobPrev;
            
            public Set(TreeNode node, boolean didRobPrev) {
                this.node = node;
                this.didRobPrev = didRobPrev;
            }
            
            @Override
            public boolean equals(Object obj) {
    	        if (obj instanceof Set) {
    			Set set = (Set) obj;
    			return this.node == set.node && this.didRobPrev == set.didRobPrev;
    		} else {
    			return false;
    		}
    	}
    		
    	@Override
    	public int hashCode() {
    		return Objects.hash(node, didRobPrev);
    	}
            
        }
        
    }
    

Log in to reply
 

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