难度: Medium
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
示例 1:
输入: root = [3,2,3,null,3,null,1] 输出: 7 解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
示例 2:
输入: root = [3,4,5,1,3,null,1] 输出: 9 解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
提示：
[1, 104] 范围内0 <= Node.val <= 104运行时间: 26 ms
内存: 18.0 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
# dp数组（dp table）以及下标的含义：
# 1. 下标为 0 记录 **不偷该节点** 所得到的的最大金钱
# 2. 下标为 1 记录 **偷该节点** 所得到的的最大金钱
dp = self.traversal(root)
return max(dp)
# 要用后序遍历, 因为要通过递归函数的返回值来做下一步计算
def traversal(self, node):
# 递归终止条件，就是遇到了空节点，那肯定是不偷的
if not node:
return (0, 0)
left = self.traversal(node.left)
right = self.traversal(node.right)
# 不偷当前节点, 偷子节点
val_0 = max(left[0], left[1]) + max(right[0], right[1])
# 偷当前节点, 不偷子节点
val_1 = node.val + left[0] + right[0]
return (val_0, val_1)
这个题解使用了树形DP的思路。对于每个节点，分别考虑偷或不偷两种情况。如果不偷当前节点，那么可以偷子节点；如果偷当前节点，那么就不能偷子节点。用一个长度为2的数组dp来记录每个节点的这两种情况的最大金钱。其中dp[0]表示不偷该节点的最大金钱，dp[1]表示偷该节点的最大金钱。然后通过后序遍历二叉树，根据左右子节点的dp数组来计算当前节点的dp数组。最后返回根节点的dp数组的最大值即可。
时间复杂度: O(n)
空间复杂度: O(h)，最坏情况下是 O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
# dp数组（dp table）以及下标的含义：
# 1. 下标为 0 记录 **不偷该节点** 所得到的的最大金钱
# 2. 下标为 1 记录 **偷该节点** 所得到的的最大金钱
dp = self.traversal(root)
return max(dp)
# 要用后序遍历, 因为要通过递归函数的返回值来做下一步计算
def traversal(self, node):
# 递归终止条件，就是遇到了空节点，那肯定是不偷的
if not node:
return (0, 0)
left = self.traversal(node.left) # 递归遍历左子树
right = self.traversal(node.right) # 递归遍历右子树
# 不偷当前节点, 偷子节点
val_0 = max(left[0], left[1]) + max(right[0], right[1])
# 偷当前节点, 不偷子节点
val_1 = node.val + left[0] + right[0]
return (val_0, val_1) # 返回当前节点的dp数组
在树形DP算法中，当遇到空节点时返回(0, 0)是因为空节点代表该处没有房子可供偷窃，因此不管是选择偷还是不偷，可获得的金额都是0。这样的设置简化了递归的边界条件处理，确保当递归到树的叶子节点的子节点时，计算不会出错，且能正确返回到上一层递归。
在计算不偷当前节点的金额时，我们有自由选择偷或不偷其左右子节点以获得最大收益。因此，对每个子节点，我们都需要比较偷和不偷两种情况的收益，并选择其中的最大值。这样做是为了确保即使不偷当前节点，也能从其子节点中获得最大的可能收益。
在计算偷当前节点的金额时，根据题目规则，如果偷了当前节点，则不能偷与其直接相连的子节点，以避免触发报警系统。因此，当选择偷取当前节点时，只能考虑左右子节点不偷的情况下的金额。这确保了算法在满足题目条件下尽可能获取最大收益。
后序遍历的方式首先处理所有子节点，然后再处理当前节点。这种遍历顺序保证了在做出是否偷窃当前节点的决定时，已经获得了所有子节点的最优偷窃策略。当选择偷窃当前节点时，会使用子节点不偷的值，确保不违反‘如果两个直接相连的房子在同一天晚上被打劫，则房屋将自动报警’的规则。这样，每一步决策都建立在已解决的子问题的基础上，保证了整个算法的正确性和效率。