My Java Solution (DP +DFS) using hashmap, easy to understand


  • 0
    A
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        private HashMap<TreeNode,Integer> taken;
        private HashMap<TreeNode,Integer> notTaken;
        public int rob(TreeNode root) {
            taken = new HashMap<>();
            notTaken = new HashMap<>();
            if(root == null){
                return 0;
            }
            helper(root);
            return Math.max(taken.get(root),notTaken.get(root));    
        }
        
        public void helper(TreeNode node){
            // System.out.println(node.val + " vvv ");
            
            int currTaken = node.val, currNotTaken = 0, a = 0, b = 0;
            if(node.left == null && node.right == null){
                taken.put(node,node.val);
                notTaken.put(node,0);
                return;
            }
            if(node.left != null){
                helper(node.left);
                a = taken.get(node.left);
                b = notTaken.get(node.left);
                currNotTaken += Math.max(a,b);
                currTaken += b;        
            }
            if(node.right != null){
                helper(node.right);
                a = taken.get(node.right);
                b = notTaken.get(node.right);
                currNotTaken += Math.max(a,b);
                currTaken += b;          
            }
            // System.out.println(node.val + " vvv ");
            // System.out.println(currNotTaken + " notttt ttt " + (currTaken));
            notTaken.put(node,currNotTaken);
            taken.put(node,currTaken);
            return;
        }
    }
    

Log in to reply
 

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