[Java] From Recursive TLE to DP Memoization AC in 4 lines
\nclass Solution {\n    public int rob(TreeNode root) {\n        if (root == null)\n            return 0;   \n        \n        int robCurrent = root.val;\n    
```\nclass Solution {\n    public int rob(TreeNode root) {\n        if (root == null)\n            return 0;   \n        \n        int robCurrent = root.val;\n        if (root.left != null)\n            robCurrent += rob(root.left.left) + rob(root.left.right);\n        if (root.right != null)\n            robCurrent += rob(root.right.left) + rob(root.right.right);\n        \n        int doNotRobCurrent = 0;\n        doNotRobCurrent += rob(root.left) + rob(root.right);\n        \n        int res = Math.max(robCurrent, doNotRobCurrent);\n        return res; \n    }\n}\n```\n\n```\nclass Solution {\n    private HashMap<TreeNode, Integer> dp = new HashMap<>();  // Line 1\n    \n    public int rob(TreeNode root) {\n        if (root == null)\n            return 0;   \n        \n        if (dp.containsKey(root))    // Line 2\n            return dp.get(root);    // Line 3\n                \n        int robCurrent = root.val;\n        if (root.left != null)\n            robCurrent += rob(root.left.left) + rob(root.left.right);\n        if (root.right != null)\n            robCurrent += rob(root.right.left) + rob(root.right.right);\n        \n        int doNotRobCurrent = 0;\n        doNotRobCurrent += rob(root.left) + rob(root.right);\n        \n        int res = Math.max(robCurrent, doNotRobCurrent);\n        dp.put(root, res);   // Line 4\n        return res;\n    }\n}\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'Java']