337. House Robber III

Approach 1: To Rob or Not to Rob

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        return max(self.helper(root))

    def helper(self, root):
        if root == None:
            return [0,0]
        if root.left == None and root.right == None:
            return [0, root.val]
        left = self.helper(root.left)
        right = self.helper(root.right)
        return [max(left) + max(right), root.val + left[0] + right[0]]

I highly recommend reading the solutions to the first 2 questions [House Robber and House Robber II] to understand this solution better.

As in the previous solutions we again use DP, but this time instead of creating arrays we just store the values on the recursion stack. We will store 2 values associated with each node namely

• sum if we rob it

• sum if we don't rob it

This way when we do a recursive depth first search in our algorithm we will see that, for each node, it's sum will be the maximum of:

• Max of left tree sum + Max of right tree sum

• Current Node value + [Sum of left sub-tree if we don't rob left child] + [Sum of right sub-tree if we don't rob right child]

This way when we reach back up top we will have the maximum value of houses that can be robbed with us

Time Complexity: O(N), where N is the number of nodes in the tree

Space Complexity: O(N)