```python # 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: # 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，称之为root。 # 除了root之外，每栋房子有且只有一个“父“房子与之相连。 # 一番侦察之后，聪明的小偷意识到 # “这个地方的所有房屋的排列类似于一棵二叉树”。 # 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。 def rob(self, root: Optional[TreeNode]) -> int: # 二叉树背景 —— 考虑用哪种遍历方式 # 后序遍历: 因为需要递归函数的返回值来做下一步计算 # 如果偷取当前节点, 左右孩子不能偷取 # 如果不偷当前节点, 左右孩子考虑偷取 # rob_( cur )返回cur节点考虑偷取的最大金额 def rob_( cur ): dp = [ 0, 0 ] if not cur: return dp left = rob_( cur.left ) right = rob_( cur.right ) # 不偷当前节点 > 左右节点偷取均可 dp[ 0 ] = max( left[ 0 ], left[ 1 ] ) + max( right[ 0 ], right[ 1 ] ) # 偷取当前节点 > 左右孩子不能偷取 dp[ 1 ] = left[ 0 ] + right[ 0 ] + cur.val return dp ans = rob_( root ) return max( ans[ 0 ], ans[ 1 ] ) ```