题目描述

一个贼找到了一片全新的地方来行窃，这片地方只有一个入口，称为root，除了root以外，其它所有房子都有且只有一个父节点。这个贼把所有房子遍历了一遍，发现他们组成了一棵二叉树！如果有两个直接相邻的房子同时被偷，就会惊动警方。

请计算这个贼在不惊动警方的情况下，最多能偷多少钱。

样例1

     3
    / \
   2   3
    \   \ 
     3   1

最多能偷 3 + 3 + 1 = 7 块钱。

样例2

     3
    / \
   4   5
  / \   \ 
 1   3   1

最多能偷 4 + 5 = 9 块钱。

算法

(树形动规) $O(n)$

典型的树形DP问题。

状态表示：

• f[i][0]表示已经偷完以 $i$ 为根的子树，且不在 $i$ 行窃的最大收益；
• f[i][1]表示已经偷完以 $i$ 为根的子树，且在 $i$ 行窃的最大收益；

状态转移：

• f[i][1]：因为在 $i$ 行窃，所以在 $i$ 的子节点不能行窃，只能从f[i->left][0]和f[i->right][0]转移；
• f[i][0]：因为不在 $i$ 行窃，所以对 $i$ 的子节点没有限制，直接用左右子节点的最大收益转移即可；

时间复杂度分析：总共有 $n$ 个状态，每个状态进行转移的计算量是 $O(1)$。所以总时间复杂度是 $O(n)$。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    unordered_map<TreeNode*, unordered_map<int, int>>f;

    int rob(TreeNode* root) {
        dfs(root);
        return max(f[root][0], f[root][1]);
    }

    void dfs(TreeNode *root)
    {
        if (!root) return;
        dfs(root->left);
        dfs(root->right);
        f[root][1] = root->val + f[root->left][0] + f[root->right][0];
        f[root][0] = max(f[root->left][0], f[root->left][1]) + max(f[root->right][0], f[root->right][1]);
    }
};