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 def __init__(self, x):
3 self.val = x
4 self.left = None
5 self.right = None
6
7class Solution:
8 def rob(self, root: TreeNode) -> int:
9 def helper(node):
10 if not node:
11 return (0, 0) # (max if not robbed, max if robbed)
12 left = helper(node.left)
13 right = helper(node.right)
14 rob = node.val + left[0] + right[0]
15 not_rob = max(left) + max(right)
16 return (not_rob, rob)
17 return max(helper(root))The helper function returns two values for each node. It uses recursion to visit each node in the tree, calculating the maximum robbery amount when the current node is included or not. For each node, if it's robbed, the children cannot be robbed; else, we take the maximum of robbing or not robbing the children. The final result is the maximum of the helper(root) values.