leetcode337 -- House Robber III

leetcode337 -- House Robber III

题目

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:

Input: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

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

Example 2:

Input: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

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


理解,这次又不一样了,这次入口只有一个,各个房子可以形成二cha树,然后相连的两个中不能够同时偷,问最终能够偷的最多的钱是多少? 这种一般要用dfs来做,因为当前的结果要依赖于其左右子树的结果.

先写解答

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def rob(self, root):
        return max(self.dfs(root))


    def dfs(self,node):
        if not node:
            return 0,0 
        l, r = self.dfs(node.left), self.dfs(node.right)
        return max(l)+max(r), node.val+l[0]+r[0]
    

定义一个dfs函数,它要返回的是一个数组,这个数组有两个元素,第一个元素返回的是没有偷当前节点的时候的最大值, 第二个元素返回的是偷了当前节点的时候的最终的最大值.下面来看一看第一个元素应该等于什么,

因为第一个元素代表没有偷当前节点的时候的最大值, 那么它的左右子节点都是可以偷,也可以不偷,所以它应该取它们各自最大值的和,即max(dfs(node.left)) + max(dfs(node.right)).

再来看第二个元素应该等于什么,

因为当前的节点偷了,那么左右子节点都是不能够偷的了,所以只能算左或子节点都没有偷的时候的最大值再加上当前加点的值, 即 dfs(node.left)[0] + dfs(node.right)[0] + node.val. 因为dfs返回的第一个元素就代表没有偷当前节点时候的最大值.(并且以当前节点作为起点的时候.)

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦