算法思路

该题为打家劫舍系列第三题，前两题均为线性DP(贴上上两题题解 LeetCode 198. 打家劫舍 和 LeetCode 213. 打家劫舍 II )。

和上两题不同，该题的DP模型为树形DP，在树形DP中，常常会出现选择结点时父节点与子节点相互制约的情况，在此题中即为不可选择两个相邻节点，根据闫氏DP分析法，我们的分析思路如下：

状态表示：

f[i][0] 表示偷完以i为根的子树，且不选择结点i的所有方案
f[i][1] 表示偷完以i为根的子树，且选择结点i的所有方案

属性：方案中金额的最大值

状态转移：

如果该结点状态为f[i][1]，表示选择该结点，所以它的左右子节点的状态必须为f[i -> left][0] 和 f[i -> right][0]，且可以同时选择；
如果该结点状态为f[i][0]，则表示并不选择该点，而左右子节点的状态没有限制，所以为了使该状态达到最大值，需要使左右子节点的状态同时也取最大值

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][0] = max(f[root -> left][0], f[root -> left][1]) + max(f[root -> right][0], f[root -> right][1]);
        f[root][1] = root -> val + f[root -> left][0] + f[root -> right][0];

    }
};