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.
1function TreeNode(val) {
2 this.val = val;
3 this.left = this.right = null;
4}
5
6var rob = function(root) {
7 const helper = (node) => {
8 if (!node) return [0, 0];
9 const left = helper(node.left);
10 const right = helper(node.right);
11 const rob = node.val + left[0] + right[0];
12 const notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
13 return [notRob, rob];
14 };
15 const result = helper(root);
16 return Math.max(result[0], result[1]);
17};The helper function calculates two states for each node using an array: helper(node)[0] for if the node isn't robbed, and helper(node)[1] for if it is robbed. This is executed recursively for every node ensuring children are not robbed when the node is robbed.