House Robber III

Problem: House Robber III

While using depth-first search to solve this problem, we calculate the best solution without the node and the best solution no matter whether the node is included or not at each node based on solution of its children nodes.

Code in Python:

# 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 dfs(self, node):
        if node == None: return (0,0)

        left_max_with, left_max_without = self.dfs(node.left)
        right_max_with, right_max_without = self.dfs(node.right)
        max_with = left_max_without + node.val + right_max_without
        max_without = left_max_with + right_max_with
        return (max(max_with, max_without), max_without)

    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        return max(self.dfs(root))