問題描述

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

思路

類似House Robber I，不過這里用recursive的方法，每個(gè)被延伸到的node都返回一個(gè)tuple, 類似由pre, cur = cur, max(cur, pre+nums[i])后的pre和cur
先判斷base case，如果不是root，返回(0, 0)
否則，一直向左右延伸；又因?yàn)槊看味加蟹祷刂?，所以用一個(gè)在延伸時(shí)，用一個(gè)變量把值存起來，用于后面返回值的計(jì)算

class Solution:
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        return self.test(root)[1]
        
    def test(self, root):
        if not root:
            return (0,0)
        if (root):
            l = self.test(root.left)
            r = self.test(root.right)
            return (l[1]+r[1], max(l[1]+r[1], l[0]+r[0]+root.val))