题目描述：

 方法一：递归

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def rob(self, root):        """        :type root: TreeNode        :rtype: int        """        def postorder(root):             if root == None:                 return (0,0)             l = postorder(root.left)             r = postorder(root.right)             return (root.val+l[1]+r[1] , max(l[0], l[1])+ max( r[0], r[1]))         r = postorder(root)         return max(r[0],r[1])

另：

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Nonecache = {} def max_with_root(node):     return node.val + max_without_root(node.left) + max_without_root(node.right) if node else 0 def max_without_root(node):     return helper(node.left) + helper(node.right) if node else 0 def helper(node):     if node in cache: return cache[node]     cache[node] = max(max_with_root(node), max_without_root(node)) if node else 0     return cache[node] class Solution(object):     def rob(self, root):         """        :type root: TreeNode        :rtype: int        """         return helper(root)