House Robber (III)

The intput represents a tree of houses with the amount to rob in each of them. The robber must maximise the amount to rob but it can't rob two directly linked houses otherwise the police will be called.

For a given node the maximum amount to rob is the maximum between the amount robbed for left and right children and the amount robbed for grandchildren plus the amount that can be rob in this node.

def rob(root: Optional[TreeNode]) -> int:
    def helper(root):
        # if a empty node is reach return (0, 0)
        if not root:
            return(0, 0)
        else:
            max_left_children, max_left_grandchildren = helper(root.left) # amount on left subtree, best amount for children and grandchildren nodes
            max_right_children, max_right_grandchildren = helper(root.right)  # amount on right subtree, best amount for children and grandchildren nodes

            max_rob_children = max_left_children + max_right_children # amount robbing left and right children
            current_max = max(max_rob_children, root.val + max_left_grandchildren + max_right_grandchildren) # best amount for this house (node)

            return(current_max, max_rob_children)

    return(helper(root)[0])