题目链接：https://leetcode.cn/problems/house-robber-iii/
难度：中等

描述：
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

题解

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution:
  8.     def rob(self, root: TreeNode) -> int:
  9.         def dfs(root):
  10.             if root is None:
  11.                 return (0, 0)
  13.             rob_left, not_rob_left = dfs(root.left)
  14.             rob_right, not_rob_right = dfs(root.right)
  16.             return root.val + not_rob_left + not_rob_right, max(rob_left, not_rob_left) + max(rob_right, not_rob_right)
  18.         return max(dfs(root))