8ms Simple Memoized solution


  • 1
    M
    public class Solution {
        
        HashMap<TreeNode,Integer> map = new HashMap<TreeNode,Integer>();
        
        public int rob(TreeNode root) {
            
        if(root == null)
        return 0;
        
        if(map.containsKey(root))
        return map.get(root);
        
        //every node will have 4 immediate grandchildren
        
        TreeNode gc_1 = root.left!=null?root.left.left:null;
        TreeNode gc_2 = root.left!=null?root.left.right:null;
        TreeNode gc_3 = root.right!=null?root.right.left:null;
        TreeNode gc_4 = root.right!=null?root.right.right:null;
        
        int sum = max(root.val + rob(gc_1) + rob(gc_2) + rob(gc_3) + rob(gc_4), rob(root.left) + rob(root.right));
        map.put(root,sum);
        return sum;
            
        }
        
        private int max(int a, int b)
        {
            return a>b?a:b;
        }
    }

Log in to reply
 

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