每日一题 337. 打家劫舍 III

难度：中等

整体思路相当于是前两天的方法倒过来，毕竟二叉树最常用的解法就是递归倒推

1. 对于每一颗子树，他必定有一种最大的盗取方法，但是只有它的 root 的盗取情况才会影响到 root 的父节点，即如果收益最大的盗取方法中不盗取 root，那么它对 root 的父节点没有任何影响
2. 简单来说，对于递归方法的返回值，我们需要返回两个值，一个是盗取 root 节点的收益最大值，一个是不盗取 root 节点的收益最大值
3. 只需返回 nl + nr + root.val和max(yl, nl) + max(yr, nr)，其中 nl 和 nr 表示 root 不盗取左右子树的根节点的情况下的最大值，yl 和 yr 表示 root 盗取左右子树的根节点的情况下的最大值
4. 当需要盗取 root 节点时，左右子树就必不能盗取；当不需要盗取 root 节点时，左右子树取两种情况的最大值

代码：

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        def crob(root):
            if root == None:
                return 0, 0
            
            yl, nl = crob(root.left)
            yr, nr = crob(root.right)

            return nl + nr + root.val, max(yl, nl) + max(yr, nr)

        return max(crob(root))
1
2
3
4
5
6
7
8
9
10
11
12