小偷又為自己的偷竊找到了一個新的地方。 該區域只有一個入口，稱為根。
除了根，每個房子都有一個且只有一個父房子。 經過一番遊覽，聰明的小偷發現這個地方所有的房子都形成了一棵二叉樹。 如果同一晚有兩間直接相連的房屋被闖入，它會自動聯繫警方。
給定二叉樹的根，返回小偷在不報警的情況下可以搶劫的最大金額。
不能同時取直接相連的兩個節點
Python
包含當前節點的val進行遞歸，以及不含節點的進行遞歸，相鄰節點不能同時取，最後兩個比較取最大值。
class Solution
def rob(self, root: TreeNode) -> int:
def dfs(root):
if not root:
return
dfs(root.left)
dfs(root.right)
f[root] = root.val + g[root.left] + g[root.right] #包含當前節點
g[root] = max(f[root.left], g[root.left]) + max(f[root.right], g[root.right]) #不含節點
f, g = defaultdict(int), defaultdict(int)
dfs(root)
return max(f[root], g[root])C++
遞歸
對於每個節點，有兩種情況：偷或者不偷。如果偷，那麼其子節點就不能偷；如果不偷，那麼其子節點可以偷也可以不偷。因此，我們可以定義一個遞歸函數 rob 來計算偷取每個節點的最大金額。
class Solution {
public:
int rob(TreeNode* root) {
pair<int, int> res = helper(root);
return max(res.first, res.second);
}
// 返回一個pair<int, int>類型的值，表示偷或者不偷該節點能獲得的最大金額
pair<int, int> helper(TreeNode* root) {
if (!root) return make_pair(0, 0);
pair<int, int> left = helper(root->left);
pair<int, int> right = helper(root->right);
// 偷該節點的最大金額等於該節點的值加上不偷其子節點的最大金額之和
int steal = root->val + left.second + right.second;
// 不偷該節點的最大金額等於其子節點的最大金額之和
int not_steal = max(left.first, left.second) + max(right.first, right.second);
return make_pair(not_steal, steal);
}
};