House Robber III

This problem involves finding the maximum amount of money that can be robbed from houses arranged in a binary tree without robbing adjacent houses. The solution uses a depth-first search (DFS) with dynamic programming to efficiently solve this.

Approach

The core idea is to use a recursive DFS function that, for each node, returns two values:

1. rob: The maximum amount of money that can be robbed including the current node.
2. not_rob: The maximum amount of money that can be robbed excluding the current node.

The recursive function works as follows:

1. Base Case: If the node is null, return (0, 0).

2. Recursive Step:

   • Recursively call the dfs function on the left and right children to get their rob and not_rob values (la, lb, ra, rb).
   • Calculate rob for the current node: This is the sum of the current node's value, and the maximum amounts that can be robbed from the left and right subtrees without robbing the children ( lb + rb).
   • Calculate not_rob for the current node: This is the maximum amount that can be robbed from the left and right subtrees, considering both options of robbing and not robbing the children (max(la, lb) + max(ra, rb)).
   • Return (rob, not_rob).

After the DFS is complete, the maximum of the rob and not_rob values for the root node is returned as the final answer. This accounts for the possibility that the root node might or might not be robbed for the maximum gain.

Time and Space Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited exactly once during the DFS traversal.
• Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack used during the DFS. In the worst case (a skewed tree), H can be equal to N. In the best case (a balanced tree), H is log(N).

Code Implementation (Python)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        def dfs(root: Optional[TreeNode]) -> (int, int):
            if root is None:
                return 0, 0
            la, lb = dfs(root.left)
            ra, rb = dfs(root.right)
            return root.val + lb + rb, max(la, lb) + max(ra, rb)
 
        return max(dfs(root))
 

The other languages (Java, C++, Go, TypeScript) follow a very similar structure, reflecting the recursive nature of the DFS and the dynamic programming approach. They all achieve the same time and space complexities.