Leetcode 337. House Robber III

Seawolf

1. 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.
   
2. 
   
3. Determine the maximum amount of money the thief can rob tonight without alerting the police.
   
4. 
   
5. Example 1:
   
6. 
   
7. Input: [3,2,3,null,3,null,1]
   
8. 
   
9.      3
   
10.     / \
    
11.    2   3
    
12.     \   \
    
13.      3   1
    
14. 
    
15. Output: 7
    
16. Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
    
17. Example 2:
    
18. 
    
19. Input: [3,4,5,1,3,null,1]
    
20. 
    
21.      3
    
22.     / \
    
23.    4   5
    
24.   / \   \
    
25. 1   3   1
    
26. 
    
27. Output: 9
    
28. Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

复制代码

1. # Definition for a binary tree node.
   
2. # class TreeNode:
   
3. #     def __init__(self, val=0, left=None, right=None):
   
4. #         self.val = val
   
5. #         self.left = left
   
6. #         self.right = right
   
7. class Solution:
   
8.     def rob(self, root: TreeNode) -> int:
   
9.         result = self.helper(root)
   
10.         return max(result)
    
11.    
    
12.     def helper(self, root: TreeNode) -> int:
    
13.         if root == None:
    
14.             return [0, 0]
    
15.         result = [0, 0]
    
16.         left = self.helper(root.left)
    
17.         right = self.helper(root.right)
    
18.         result[0] = max(left) + max(right)
    
19.         result[1] = left[0] + right[0] + root.val
    
20.         return result

复制代码