https://leetcode.com/problems/house-robber-iii

If you already solved House Robber I or II, you probably aware, that this problem is about dp. However, let us look at it from a bit different point of view, it will be much easier to digest: let us use dfs and for each node we will keep two values:

  1. Maximum gain we can get if we already visited all subtree given node, if we rob given node.
  2. Maximum gain, we can get if we already visited all subtree given node, if we do not rob given node.

How we can find it, using recursion now? Imagine, that we have node and L and R are left and right children. Then:

  1. If we rob given node, than we can not rob children, so answer will be node.val + L[1] + R[1]
  2. If we do not rob house, we have two options for L and two options for R, and we choose the best ones, so we have max(L) + max(R).

Complexity: time complexity is O(n), because we visit all our tree. Space complexity is O(h), because we use recursion.

class Solution:
    def rob(self, root):
        def dfs(node):
            if not node: return [0, 0]
            L = dfs(node.left)
            R = dfs(node.right)
            return [node.val + L[1] + R[1], max(L) + max(R)]
        
        return max(dfs(root))

If you like the solution, you can upvote it on leetcode discussion section: Problem 0337