Sponsored
Sponsored
This approach uses recursion along with memoization to store the maximum robbery amount for each node of the tree. The idea is to leverage a helper function that returns two values for each node: maximum money if the current node is included and maximum money if the current node is not included. At each node, we have two choices: either rob this node or not rob it, and for each choice, there are further choices for child nodes and so on.
Time Complexity: O(N), where N is the number of nodes in the tree, as each node is visited only once. Space Complexity: O(N) due to the recursion stack space in the worst case of a skewed tree.
1class TreeNode {
2 int val;
3 TreeNode left;
4 TreeNode right;
5 TreeNode(int x) { val = x; }
6}
7
8class Solution {
9 public int rob(TreeNode root) {
10 int[] result = robSub(root);
11 return Math.max(result[0], result[1]);
12 }
13
14 private int[] robSub(TreeNode node) {
15 if (node == null) return new int[2];
16
17 int[] left = robSub(node.left);
18 int[] right = robSub(node.right);
19
20 int rob = node.val + left[0] + right[0];
21 int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
22
23 return new int[] {notRob, rob};
24 }
25}The Java solution also uses a recursive helper function to determine the maximum funds that can be robbed with and without robbing each node. It creates an array to hold the values for easily returning multiple results to the parent nodes.