首页 > 代码库 > 337. House Robber III——树的题目几乎都是BFS、DFS，要么递归要么循环

337. House Robber III——树的题目几乎都是BFS、DFS，要么递归要么循环

2024-08-29 08:11:19   217人阅读

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.

Example 1:

     3
    /    2   3
    \   \ 
     3   1

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

     3
    /    4   5
  / \   \ 
 1   3   1

Maximum amount of money the thief can rob = 4 + 5 = 9.

# 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
        3 => 3
        3 => 3
       /
      2
        3
                   3 =>3=max(3,3)
        3
       / \  => 3+2=5=max(3, 2+3)
      2   3
     3
    /    2   3
    \    
     3    => 3+3=6=max(3+3,2+3)=max(3+node2,3 not choose, node2,3 choosed)
     1
    /    4   1
  / \   \ 
 1   1   5 => 4+5=9=max(3+3+1+1,4+5)=9 
        """
        return max(self.rob_helper(root))
    
    def rob_helper(self, root):
        if root is None:
            return [0, 0]
        ans = [0]*2
        ans_left = self.rob_helper(root.left)
        ans_right = self.rob_helper(root.right)
        ans[0] = max(ans_left[0], ans_left[1]) + max(ans_right[0], ans_right[1])
        ans[1] = ans_left[0] + ans_right[0] + root.val
        return ans

 

337. House Robber III——树的题目几乎都是BFS、DFS，要么递归要么循环


联系
我们