[ 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 )