JAVA | 3 Approaches | Recursion | DP | Greedy | Detailed Explanation
Intution: Since we have to start with root and we can\'t rob two directly-linked houses. We have two cases:\n Case1: If we rob the root node - Then we can\'t ro
**Intution:** Since we have to start with root and we can\'t rob two directly-linked houses. We have two cases:\n* **Case1:** If we rob the root node - Then we can\'t rob the child nodes of root but we can rob the 4 grandchildren of the root (i.e., root.left.left, root.left.right, root.right.left, root.right.right).\n* **Case2:** If we don\'t rob the root node - Then we can rob the 2 children of root (i.e., root.left, root.right).\nAnd our answer will be maximum of the two cases.\nFor Example:\n ```\n1.)     3                                            2.)           3\n        / \\                                                        /  \\\n       2   3                                                      4    5\n        \\   \\                                                    / \\   /  \n         3   1                                                  1   3 1\n\tHere rob the root node and its grandchildren       Here better will be to rob the child nodes of \n\ti.e., (3+3+1) = 7                                  root i.e., (4+5)=9.  \n\tHere Case1 will give 5(2+3) < 7                    Here Case2 will give 8(3+1+3+1) < 9\n```\nNow after all the discussion lets start with approach starting from recursion and will optimize as much possible.\n\n**Approach1: Recursive (TLE)**\nT.C : O(2^n)\nS.C : O(1) (ignoring stack memory used for recursion)\n```\nclass Solution{\n    public int rob(TreeNode root) {\n        if (root == null) return 0;\n\n        int ans = 0;\n\t\t\n\t\t// max value from left grandchildren\n        if (root.left != null) {\n            ans += rob(root.left.left) + rob(root.left.right);\n        }\n\t\t\n\t\t// max value from right grandchildren\n        if (root.right != null) {\n            ans += rob(root.right.left) + rob(root.right.right);\n        }\n\n        return Math.max(ans + root.val, rob(root.left) + rob(root.right));  //(Case1,Case2)\n    }\n}\n```\n\n**Approach2: Rucrsion Using HashMap**\nT.C : O(n)\nS.C. : O(n)\n**Explanation:** If you observe the recursive approach we have overlapping subproblems like for root node we are calling on its grandchildren (root.left.left, root.left.right, root.right.left, root.right.right) and when we are on child node of root (root.left, root.right) then again we will need the data of those four nodes so again calling on it. So here you have **Recusrion+Overlapping SubProblems** which can make you think of DP Approach.\nSo what we are doing is just store the calculated answer for each node int the HashMap and if we need the value for that node again at any point we will just do the map.get(node) and get the value. Rest Recursive logic is absolutely same.\n```\nclass Solution{\n    public int rob(TreeNode root) {\n        return rob(root, new HashMap<>());\n    }\n\n    public int rob(TreeNode root, Map<TreeNode, Integer> map) {\n        \n        if (root == null) return 0;\n\n        if (map.containsKey(root)) return map.get(root);\n\n        int ans = 0;\n\n        if (root.left != null) {\n            ans += rob(root.left.left, map) + rob(root.left.right, map);\n        }\n\n        if (root.right != null) {\n            ans += rob(root.right.left, map) + rob(root.right.right, map);\n        }\n\n        ans = Math.max(ans + root.val, rob(root.left, map) + rob(root.right, map));\n        map.put(root, ans);\n\n        return ans;\n    }\n}\n```\n\n**Approach3: Greedy Approach** \nT.C. : O(n)\nS.C. : O(1)\n**Explanation:** Since we can now say that for each node we need only two data is required that is what will be the max value if that node is robbed and whats the max value if the node is not robbed.\nSo why not just keep the array of two elements of which first element have the data if that node is not robbed and second element has the data if that node is robbed.\nSo at last we have to return max of first and second element data stored for root. And this makes it a greedy approach.\n\n**More Explanation:** So in the below code how we are filling ans[0]  and ans[1]:\n1.) Since ans[0] will have the value if root is not robbed, so we are concerned just about the root.left and root.right data which is in left and right array. Now we want max value so we need to check both Cases for both left and right that which Case will give max value \n* left[0],right[0] -> indicates that while calculating, left and right node were not robbed and it has value from its child nodes \n* left[1],right[1] -> indicates that left and right were robbed so they have data from their grandchildren also.\nAnd we need max of the two cases for both left and right.\n\n2.) Now ans[1] will have the value if root is robbed then we can\'t rob root\'s children but we can can rob its grandchildren and left[0] and right[0] have data in which left and right were not robbed that is root\'s children were not robbed. So our value will be root.val + left[0] + right[0].\nAnd at last max of ans[0] and ans[1] will be answer.\n```\nclass Solution {\n    public int rob(TreeNode root) {\n        int ans[] = robHouse(root);\n        return Math.max(ans[0],ans[1]);\n    }\n    \n    public int[] robHouse(TreeNode root){\n        if(root==null){\n            return new int[2];\n        }\n        \n        int left[] = robHouse(root.left);\n        int right[] = robHouse(root.right);\n        \n        int ans[] = new int[2];\n        \n        ans[0] = Math.max(left[0],left[1])+Math.max(right[0],right[1]);\n        ans[1] = root.val+left[0]+right[0];\n        \n        return ans;\n    }\n}\n```\n \n* I hope the explanation helped you...Thanks!!
['Greedy', 'Recursion', 'Java']