337.House Robber III

House Robber III
第一次思考结果是直接将数的奇数层与偶数层分别求和，比大小得出结果：

class Solution {
public:
    void tranversal(bool layer,int& oValue,int& eValue,TreeNode* root)
    {
        if(root == NULL)
        {
            return;
        }
        if(layer)//奇数层
        {
            oValue +=root->val;
        }
        else
        {
            eValue +=root->val;
        }
        tranversal(!layer,oValue,eValue,root->left);
        tranversal(!layer,oValue,eValue,root->right);
    }
    int rob(TreeNode* root) {
        int oValue = 0;
        int eValue = 0;
        tranversal(true,oValue,eValue,root);
        return oValue > eValue? oValue:eValue;
    }
};

[4,1,null,2,null,3]，面对这样一个测试，理所当然就错了。
换一个思路，如果将每层的和保存成一个数组，就转化为在不能有相邻位置同时被选取的情况下，求数组的最大和，并且该数组元素中没有负值。
OK，第二版：

class Solution {
public:
    void tranversal(int layer, vector<int>& buffer,TreeNode* root)
    {
        if(root == NULL)
        {
            return;
        }
        if(buffer.size() == layer)
        {
            buffer.push_back(0);
        }
        buffer[layer]+=root->val;
        tranversal(layer+1,buffer,root->left);
        tranversal(layer+1,buffer,root->right);
    }
    int rob(TreeNode* root) {
        vector<int> buffer;
        int layer = 0;
        tranversal(layer,buffer,root);
        buffer.push_back(0);
        buffer.push_back(0);
        buffer.push_back(0);
        int sum = 0;
        for(int i = 0; i < buffer.size() - 3;i+=2)
        {
            if(buffer[i] >= buffer[i+1] ||buffer[i] + buffer[i+2] >= buffer[i+1] + buffer[i+3])
            {
                sum+=buffer[i];
            }
            else
            {
                sum+=buffer[i+1];
                ++i;
            }
        }
        return sum;  
    }
};

[2,1,3,null,4]，又错了。。
= =
一开始题意就想偏了，看来是某种遍历，之后在处理，想想。。
OH，看到提示标签了，原来是DFS，真的是蠢。
第三版：

class Solution {
public:
    map<TreeNode*,int> steal;
    map<TreeNode*,int> refuse;
    int rob(TreeNode* root) 
    {
        DFStranversal(root);
        return max(steal[root],refuse[root]);
    }
    void DFStranversal(TreeNode* root)
    {
        if(root == NULL) return;
        DFStranversal(root->left);
        DFStranversal(root->right);
        steal[root] = root->val + refuse[root->left] + refuse[root->right];
        refuse[root] = max(max(steal[root->left]+
                 steal[root->right],steal[root->left]+
                 refuse[root->right]),
                  max(refuse[root->left]+steal[root->right],
                  refuse[root->left]+refuse[root->right]));
    }
};

从根节点开始进行深度优先遍历，每个节点有小偷去偷和拒绝偷两种情况，应该采纳的情况是两者中的较大值。