程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> (LeetCode OJ) 337. House Robber III

(LeetCode OJ) 337. House Robber III

編輯:關於C++
Total Accepted:1341Total Submissions:3744Difficulty: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.

Credits:
Special thanks to@dietpepsifor adding this problem and creating all test cases.

Subscribeto see which companies asked this question

Show Tags Show Similar Problems

分析:

下面的答案有錯,不知道錯在哪裡!!!難道不是統計偶數層的和與奇數層的和,然後比較大小就可得出結果?

/**
 * 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; ileft != 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);
}
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved