house-robber-iii

这道题略有难度，题目链接。题目要求就是求一个二叉树所有节点数值的和的最大值，条件是有边连接的两个节点不能被同时选中。一开始没什么思路，在网上看了别人的思路之后(并没有参考别人的代码)，知道了用动态规划的思想（？我也不确定这是不是动态规划的算法）。
代码思路为：从root开始遍历，有两种可能的情况，包含root节点但不包含root的左孩子节点和右孩子节点，第二种情况是不包含root节点但包含root的左孩子节点和右孩子节点。故使用一个max就可以解决这个问题。为了把之前已经计算过的节点的子树的最大值保存起来，在类里使用了一个map私有变量。注意这个map变量不能放在dfs中作为static变量，一开始我是这么做的。后来发现这种情况下行不通，因为leetcode平台测试的时候应该是生成了多个Solution类的实例，会导致前几个测试用例可以通过，大概从第四个开始就报错。一开始我很不理解为什么会报错，因为相同的用例我用run code的时候输出的结果是正确的，commit的时候就会报错。最后发现是这个私有static变量的问题。贴出代码如下

class Solution {
public:
    map<TreeNode*, int> m;
    int rob(TreeNode* root) {
        return dfs(root);
    }
    
    int dfs(TreeNode* root) {
        if(!root)
            return 0;
        if(m.find(root) == m.end()) {
            int left = root->left == NULL ?  0 : (dfs(root->left->left) + dfs(root->left->right));
            int right = root->right == NULL ? 0 : (dfs(root->right->left) + dfs(root->right->right));
            
            m[root] = root->val + (left) + (right);
            cout << root->val << "\t" << m[root] << endl;
        }
        return max(m[root], dfs(root->left) + dfs(root->right));
    }
};