The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.
Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.
Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.
Example 1:
Input: root = [3,2,3,null,3,null,1] Output: 7 Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
Input: root = [3,4,5,1,3,null,1] Output: 9 Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.
Constraints:
[1, 104].0 <= Node.val <= 104This 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.
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.
C++
JavaScript
C#
Java
C
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.
House Robber - Leetcode 198 - Python Dynamic Programming • NeetCode • 377,825 views views
Watch 9 more video solutions →Practice House Robber III with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor