<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)


相关推荐

  • 浓缩就是精华「建议收藏」

    浓缩就是精华「建议收藏」 『凡人牧场』人生启示录:被称为世上最经典的25句话(转载)   作者:晶晶鱼 提交日期:2003-12-3115:32:40    1,记住该记住的,忘记该忘记的。改变能改变的,接受不能改变的。      2,能冲刷一切的除了眼泪,就是时间,以时间来推移感情,时间越长,冲突越淡,仿佛不断稀释的茶。      3,怨言是上天得至人类最大的供物,也是人

  • 基于 mysql时序_时序数据库简介

    基于 mysql时序_时序数据库简介时间序列数据库简称时序数据库(TimeSeriesDatabase),用于处理带时间标签(按照时间的顺序变化,即时间序列化)的数据,带时间标签的数据也称为时间序列数据。时序数据的几个特点1.基本上都是插入,没有更新的需求。2.数据基本上都有时间属性,随着时间的推移不断产生新的数据。3.数据量大,每秒钟需要写入成千万上亿条数据业务方常见需求1.获取最新状态,查询最近的数据(例如传感器最新…

  • 什么是robots.txt文件

    什么是robots.txt文件一、什么是robots文件Robots.txt文件是网站跟爬虫间的协议,对于专业SEO并不陌生,用简单直接的txt格式文本方式告诉对应的爬虫被允许的权限,也就是说robots.txt是搜索引擎中访问网站的时候要查看的第一个文件。当一个搜索蜘蛛访问一个站点时,它会首先检查该站点根目录下是否存在robots.txt,如果存在,搜索机器人就会按照该文件中的内容来确定访问的范围;如果该文件不存在,所有的搜索蜘蛛将能够访问网站上所有没有被口令保护的页面。如您的网站未设置robots协议,搜索引擎对网.

  • 汇编学习 安装DOSBOX及debug.exe教程

    相信有很多小伙伴跟我一样,在学习汇编时却发现win764位系统下是无法使用debug.exe的,因为win7x64没有debug.exe这个文件,因此需要安装DOSBOX。需要下载地址的可到我的资源中查找。下面开始安装教程:1.下载后解压并安装DOSBOX,最好安装在c盘以外的盘,下面以安装在d盘为例2.将MASM文件夹移到d盘根目录下3.打开DOSBOX,这时会出现两个窗

  • a算法解决八数码实验报告_人工智能常用算法模型

    a算法解决八数码实验报告_人工智能常用算法模型实验一A*算法求解8数码问题一、实验目的熟悉和掌握启发式搜索的定义、估价函数和算法过程,并利用A*算法求解N数码难题,理解求解流程和搜索顺序。二、实验原理A*算法是一种启发式图搜索算法,其特点在于对估价函数的定义上。对于一般的启发式图搜索,总是选择估价函数f值最小的节点作为扩展节点。因此,f是根据需要找到一条最小代价路径的观点来估算节点的,所以,可考虑每个节点n的估价函数值为两个分量:从起始节点到节点n的实际代价g(n)以及从节点n到达目标节点的估价代价h(n),且hn≤h*n,h*n

    2022年10月31日
  • jedispool 连接池_redis-cli连接redis数据库

    jedispool 连接池_redis-cli连接redis数据库一、连接前的准备1.确保windows能够ping通linux,linux能够ping通windows。2.开放CentOS7的端口6379。firewall-cmd–add-port=6379/tcp–permanent3.注释掉redis.conf文件中的bind。#bind127.0.0.14….

发表回复

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

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