Total Accepted: 1341 

Total Submissions: 3744 

Difficulty: Medium

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root."

 Besides the root, each house has one and only one parent house. 

After a tour, the smart thief realized that "all houses in this place forms a binary tree". 

It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

3    / \   2   3    \   \      3   1

Maximum amount of money the thief can rob = 

3 + 

3 + 

1 = 

7.

Example 2:

3    / \   4   5  / \   \  1   3   1

Maximum amount of money the thief can rob = 

4 + 

5 = 

9.

分析：

以下的答案有错，不知道错在哪里！

！

！难道不是统计偶数层的和与奇数层的和，然后比較大小就可得出结果？

/** * 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:    int rob(TreeNode* root) {        if(root==NULL)              return 0;          queue
     
       que;//用来总是保存当层的节点          que.push(root);          int oddsum =root->val;//用于统计奇数层的和        int evensum=0;  //用于统偶数层的和        //获取每一层的节点        int curlevel=2;        while(!que.empty())          {              int levelSize = que.size();//通过size来推断当层的结束              for(int i=0; i
      
       left != NULL) //先获取该节点下一层的左右子，再获取该节点的元素。由于一旦压入必弹出。所以先处理左右子                      que.push(que.front()->left);                  if(que.front()->right != NULL)                       que.push(que.front()->right);                  if(curlevel % 2 ==1)                    oddsum  += que.front()->val;                else                    evensum += que.front()->val;                que.pop();              }              curlevel++;        }        return oddsum > evensum ? oddsum : evensum;//奇数层的和与偶数层的和谁更大谁就是结果    }};
      
     

学习别人的代码：

int rob(TreeNode* root) {    int child = 0, childchild = 0;    rob(root, child, childchild);    return max(child, childchild);}void rob(TreeNode* root, int &child, int &childchild) {    if(!root) return;    int l1 = 0, l2 = 0, r1 = 0, r2 = 0;    rob(root->left, l1, l2);    rob(root->right, r1, r2);    child = l2 + r2 + root->val;    childchild = max(l1, l2) + max(r1, r2);}

注：本博文为原创，兴许可能继续更新本文。假设转载，请务必复制本条信息！

原文地址：http://blog.csdn.net/ebowtang/article/details/50890931

原作者博客：http://blog.csdn.net/ebowtang

：http://blog.csdn.net/ebowtang/article/details/50668895