<LeetCode OJ> 337. House Robber III

<LeetCode OJ> 337. House Robber III

大家好,又见面了,我是全栈君。

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<TreeNode*> 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<levelSize; i++)   
            {  
                if(que.front()->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);
}

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

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

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

本博客LeetCode题解索引:http://blog.csdn.net/ebowtang/article/details/50668895

转载于:https://www.cnblogs.com/yutingliuyl/p/7225828.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/108303.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 计算机组成原理知识点梳理(一)

    计算机组成原理知识点梳理(一)注:所学教材为《计算机组成原理(第二版)》唐朔飞编著;本次梳理涵盖内容为:第一章计算机系统概论1.1计算机系统简介1.2计算机的基本组成参考内容以及图片来源为书本和csdn博文第一章计算机系统概论1.1计算机系统简介计算机系统结构:主要研究软硬件功能的分配和对软硬件界面的确定。计算机组成是计算机系统结构的逻辑实现。计算机实现是对计

  • QT多线程中槽函数如何执行分析「建议收藏」

    周末天冷,索性把电脑抱到床上上网,这几天看了dbzhang800博客关于Qt事件循环的几篇Blog,发现自己对Qt的事件循环有不少误解。从来只看到现象,这次借dbzhang800的博客,就代码论事,因此了解到一些Qt深层的实现,虽然是在Qt庞大的构架里只算的是冰山的一角,确让人颇为收益。从dbzhang800的博客中转载两篇关于事件循环的文章,放…

  • 免费的ssl证书申请_公需课怎么申请证书

    免费的ssl证书申请_公需课怎么申请证书第一步:在阿里云上申请免费的https证书先点击Symantec然后选择1个域名然后选择免费型DVSSL第二步:我的订单页面完成信息的补全第三步:点击详情查看DNS信息,并且配置DNS信息第四步:下载证书,上传到nginx服务器第五步:配置nginx代理,并重启nginx服务第六步:访问https的接口或者页面,查看是否配置正确。

  • python模拟键盘输入_python控制鼠标键盘

    python模拟键盘输入_python控制鼠标键盘win32api.keybd_event该函数原型:keybd_event(bVk,bScan,dwFlags,dwExtraInfo)第一个参数:虚拟键码(键盘键码对照表见附录);第二个参数:硬件扫描码,一般设置为0即可;第三个参数:函数操作的一个标志位,如果值为KEYEVENTF_EXTENDEDKEY则该键被按下,也可设置为0即可,如果值为KEYEVENTF_KEYUP则该按键被释放;…

    2022年10月11日
  • C语言int的取值范围_c语言int表示范围

    C语言int的取值范围_c语言int表示范围C语言int的取值范围我们常常看到int取值范围为-32768~32767,实际上int的取值范围依赖于计算机系统,在16位机器中,int占16位,取值范围为前面所说的-32768~32767(-2^16~2^16-1)。而在32位和64位机器中,int占32位,取值范围为-2147483648~2147483647(-2^32~2^32-1)。ISO/ANSIC规定,int类型的最小范围为……

  • 全网最详细ENSP安装教程,零基础网工小白必看![通俗易懂]

    全网最详细ENSP安装教程,零基础网工小白必看![通俗易懂]全网最详细ENSP安装教程,零基础网工小白必看!学习更多网络技术,扫码即可免费报名听课,更多资料加QQ群414605852材料准备在下载ENSP之前先安装这3个软件1.1.安装WinPcap1.2.安装Wireshark1.3.安装VirtualBoXENSP安装2.1.软件安装2.2.设备注册在注册设备之前,先保证没有任何设备在界面上然后点击菜单—>工具—>注册设

    2022年10月14日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号