leetcode_337

发表于   |   分类于

House Robber III

题目戳这

题意

题意是给定一颗二叉树，树上的每个节点都有一个值，现在将符合条件的节点值加起来要求最大，条件指的是任意两个节点不能相邻(也就是在二叉树上没有边直连)

解法

这道题目的题解相当的详细，学到了不少东西。稍微总结下。

(1)首先我们来讨论最简单的版本。

题目要求的是不能相邻的所有点最大值，那么我们就可以想到，对于每一个点，要么取要么不取。如果取了，那么我们就得跳过它的直接左右节点，如果不取，那么我们可以取或者不取它的左右节点，注意了，这里不一定就取左右节点，因为取左右节点这个事儿是不仅仅涉及到当前的根节点，还会影响下一层的节点取值。这里我们可以将左右子树当做递归参数进行递归计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        val = 0
        if root.left:
            val += self.rob(root.left.left) + self.rob(root.left.right)
        if root.right:
            val += self.rob(root.right.left) + self.rob(root.right.right)
        return max(root.val + val, self.rob(root.left) + self.rob(root.right))

(2)仔细思考，其实在第一个版本的代码中我们做了好多重复的工作，比如求root这一层最大值，那我们要求root.left,root.right,root.left.left,root.left.right, root.right.left……..，而当求root.left时，我们又得求root.left.left,root.left.right……，这样很多都是重复求解了。在这里我们可以用记忆化搜索，用map来存储当前节点已经求得的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def dfs(self, root, mp):
        if not root:
            return 0
        if root in mp:
            return mp[root]
        val = 0
        if root.left:
            val += self.rob(root.left.left) + self.rob(root.left.right)
        if root.right:
            val += self.rob(root.right.left) + self.rob(root.right.right)
        res = max(root.val + val, self.rob(root.left) + self.rob(root.right))
        mp[root] = res
        return res
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        return self.dfs(root, {})

(3)第二个版本其实已经挺快了，每个点只要求一次，不过如果用python的这个代码的话，因为运行比较慢，还是通不过。。这时候神奇的第三个版本代码就出来了。。

第三个版本用了贪心的思想，，不用存储每个点的最大值，因为这样子还是要每个点都遍历到，还是有些慢，现在我们只要存储当前节点的两个结果就行，第一个结果就是当取这个点的值时能够得到的最大值，第二个结果就是不取当前点时能够得到的最大值。这样子搜到最后时，一层一层往上回溯就可以了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 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 dfs(self, root):
        if not root:
            return [0]*2
        
        left = self.dfs(root.left)
        right = self.dfs(root.right)
        
        res = [0]*2 # res[0]代表不取当前root值时的最大值，res[1]代表取当前root值时的最大值
        
        res[0] = max(left[0],left[1]) + max(right[0], right[1])
        res[1] = root.val + left[0] + right[0]
        
        return res
        
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        ans = self.dfs(root)
        return max(ans[0],ans[1])