Java bottom-up and top-down solutions using DP
The naive solution is straightforward, just traverse the tree and in each node, we either take it or not.  If we take it, we cannot take its children, if not ta
The naive solution is straightforward, just traverse the tree and in each node, we either take it or not.  If we take it, we cannot take its children, if not take, we can take either or both of the children.  This will cause TLE due to extra calculation.  Since this is a house robber problem, DP is the first come to mind for optimization.  There are two ways to work with this problem.  The top-down is the most intuitive one for me, as follows.  Used two map, hasRoot and noRoot, since we need to keep track of the result for either rob the house or not. \n\nThe second approach is bottom-up.  It is not very intuitive for a tree.  But one can think about post-order traversal.  We traverse the left and the right child and return some necessary result, and then process the root.  First, what do we need the child to return?  So from the first solution, we can see that we either rob a house or not, so the child needs to return two values, *rob* or *no rob* for the root.  Here we can just use an int array to keep the two values.   `// traverse the tree   int[] left = helper(curr.left); int[] right = helper(curr.right);`  Here left[0] represents robbing root node, left[1] not robbing.  \n\nThen we do stuff for the root node.   We need an int array again to save its result.  We either rob root, and take the `left[1]` and `right[1]` and add root value to it, or we don't rob root, and take the largest one for left and right.  In the end, we just return res.  \n\nHere are two solutions, hope it helps!\n\n\nTop-down approach:\n\n        Map<TreeNode, Integer> hasRoot = new HashMap<>();\n        Map<TreeNode, Integer> noRoot = new HashMap<>();\n        public int rob(TreeNode root) {\n            if (root == null) {\n                return 0;\n            }\n            int max = Math.max(helper(root, true), helper(root, false));\n            return max;\n        }\n    \n        private int helper(TreeNode root, boolean canrob) {\n            if (root == null) {\n                return 0;\n            }\n            int res = 0;\n            if (canrob) {\n                // check the hasRoot map for previous calculated\n                if(hasRoot.containsKey(root)) {\n                    return hasRoot.get(root);\n                }\n                res = Math.max(helper(root.left, false) + helper(root.right, false) + root.val, helper(root.left, true) + helper(root.right, true));\n                hasRoot.put(root, res);\n            } else {\n                // check the noRoot map\n                if(noRoot.containsKey(root)) {\n                    return noRoot.get(root);\n                }\n                res = helper(root.left, true) + helper(root.right, true);\n                noRoot.put(root, res);\n            }\n            return res;\n        }\n\n\nBottom-up:\n\n        // bottom-up solution\n        public int rob(TreeNode root) {\n            int[] num = helper(root);\n            // nums[0] includes root, nums[1] excludes root\n            return Math.max(num[0], num[1]);\n        }\n        private int[] helper(TreeNode curr) {\n            if (curr == null) {\n                return new int[2];\n            }\n            // traverse the tree\n            int[] left = helper(curr.left);\n            int[] right = helper(curr.right);\n            \n            // do stuff\n            \n            int[] res = new int[2];\n            // case 1:  add root value, so exclude both left and right\n            res[0] = left[1] + right[1] + curr.val;  \n            // case 2: exclued root value, get max from both left child and right child\n            res[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);  \n            \n            // done stuff\n            \n            return res;\n        }
[]