Two easy understanding recursive solutions with HashMap memory


  • 0
    T

    Solution1:

    Map<TreeNode, Integer> Optimalmap; //Store the optimal result for each root
    Map<TreeNode, Integer> NonRobmap;//Store the optimal result for each root, if we don't rob it
    public int rob(TreeNode root) {
        this.Optimalmap = new HashMap<TreeNode, Integer>();
        this.NonRobmap = new HashMap<TreeNode, Integer>();
        return robHelper(root,true);
    }
    public int robHelper(TreeNode root, boolean canRob) {        
        int result = 0;
        if(root!=null){
            if(canRob) {//if root can be robbed, we can rob it or not, and there exists an optimal choice 
                if(Optimalmap.containsKey(root)) return Optimalmap.get(root);
                //We can rob it 
                int RobIt = root.val+robHelper(root.left,false)+robHelper(root.right,false);
                if(!NonRobmap.containsKey(root)) //We don't rob it
                    NonRobmap.put(root,robHelper(root.left,true)+robHelper(root.right,true));   
                int notRobIt = NonRobmap.get(root);
                result = Math.max(RobIt,notRobIt); //Optimal result is the maximum of (RobIt,notRobIt)
                Optimalmap.put(root,result);
            }
            else {//if root can't be robbed
                if(NonRobmap.containsKey(root)) return NonRobmap.get(root);
                result = robHelper(root.left,true)+robHelper(root.right,true);
                NonRobmap.put(root,result);
            }
        }        
        return result;
    }
    

    Solution2:

    Map<TreeNode, Integer> Robmap;//Store the optimal result for each root, if we rob it
    Map<TreeNode, Integer> NonRobmap;//Store the optimal result for each root, if we don't rob it
    public int rob(TreeNode root) {
        this.Robmap = new HashMap<TreeNode, Integer>();
        this.NonRobmap = new HashMap<TreeNode, Integer>();
        return robHelper(root,true);
    }
    public int robHelper(TreeNode root, boolean canRob) {        
        int result = 0;
        if(root!=null){
            if(canRob) {//if root can be robbed, we can rob it or not                                
                if(!Robmap.containsKey(root)) //We can rob it
                    Robmap.put(root,root.val+robHelper(root.left,false)+robHelper(root.right,false));   
                int RobIt = Robmap.get(root);
                if(!NonRobmap.containsKey(root)) //We can not rob it
                    NonRobmap.put(root,robHelper(root.left,true)+robHelper(root.right,true));   
                int notRobIt = NonRobmap.get(root);
                result = Math.max(RobIt,notRobIt); //Optimal result is the maximum of (RobIt,notRobIt)
            }
            else {//if root can't be robbed, we 
                if(NonRobmap.containsKey(root)) return NonRobmap.get(root);
                result = robHelper(root.left,true)+robHelper(root.right,true);
                NonRobmap.put(root,result);
            }
        }        
        return result;
    }

Log in to reply
 

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