[ LeetCode ] 337. House Robber III

# 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        """        res = [0]
        d = {}

        def dfs(node):            if not node:                return 0
            if node in d:                return d[node]

            col_1 = dfs(node.left) + dfs(node.right)
            col_2 = node.val
            if node.left:                col_2 += dfs(node.left.left) + dfs(node.left.right)
            if node.right:                col_2 += dfs(node.right.left) + dfs(node.right.right)

            d[node] = max(col_1, col_2)

            return max(col_1, col_2)

        return dfs(root)