Could any one tell me why I am wrong? The code is selfexplainatory 40/124 test case passed


  • 0
    F
    public class Solution {
        private Map<TreeNode, Integer> _map = new HashMap<>();
        public int rob(TreeNode root) {
            return Math.max(rob(root, true), rob(root ,false));
        }
        
        private int rob(TreeNode root, boolean allow){
            if(root == null) return 0;
            if(_map.containsKey(root)) return _map.get(root);
            int ans = 0;
            if(allow){
                ans = Math.max(root.val + rob(root.left, false) + rob(root.right, false),
                                    rob(root.left, true) + rob(root.right, true));    
            }
            else{
                ans = rob(root.left, true) + rob(root.right, true);
            }
            _map.put(root, ans);
            return ans;
        }
    }
    

  • 0
    A

    @feng4 Your _map cache tries to answer question how much you can rob from a certain node, only based on the node.

    The answer would be different depending on whether you are allowed to rob a certain node, or whether you just had rob a previous direct link.

    That is the main problem.

    Either you have separate map of <TreeNode, Integer> for each of allowed vs not allowed case, or you have a map from a pair of TreeNode + allowed to an integer.


Log in to reply
 

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