337. 打家劫舍 III

https://leetcode-cn.com/problems/house-robber-iii/

一：前序遍历

1、直接遍历：超时

class Solution:
    def rob(self, root: TreeNode) -> int:
        if root==None:
            return 0
        #抢root，然后去下下家
        if root.left == None and root.right == None:    #左右都为空
            do = root.val
        elif root.left == None:  #只有左边为空
            do = root.val + self.rob(root.right.left) + self.rob(root.right.right)
        elif root.right == None:  # 只有右边为空
            do = root.val + self.rob(root.left.left) +  self.rob(root.left.right)
        else:   #都不为空
            do = root.val + self.rob(root.left.left) + self.rob(root.left.right) + self.rob(root.right.left) + self.rob(root.right.right)
        #不抢，然后去下家
        not_do = self.rob(root.left) + self.rob(root.right)

        res =max(do, not_do)
        return res

2、使用备忘录

在1中打印每次的do和not_do以及节点序号，发现存在很多重复访问，当每个节点的遍历走到res时，已经计算完毕，之后再次计算也是同样的结果，因此用一个备忘录保存，避免重复计算

class Solution:
    memo = {}   #全局备忘录
    def rob(self, root: TreeNode) -> int:
        if root==None:
            return 0
        if root in self.memo:   #该节点已有结果，直接返回
            return self.memo[root]
        #抢root，然后去下下家
        if root.left == None and root.right == None:    #左右都为空
            do = root.val
        elif root.left == None:  #只有左边为空
            do = root.val + self.rob(root.right.left) + self.rob(root.right.right)
        elif root.right == None:  # 只有右边为空
            do = root.val + self.rob(root.left.left) +  self.rob(root.left.right)
        else:   #都不为空
            do = root.val + self.rob(root.left.left) + self.rob(root.left.right) + self.rob(root.right.left) + self.rob(root.right.right)
        #不抢，然后去下家
        not_do = self.rob(root.left) + self.rob(root.right)

        res =max(do, not_do)
        self.memo[root] = res   #记入备忘录
        return res