当前位置: 首页 > news >正文

LeetCode 1315.祖父节点值为偶数的节点和

给你一棵二叉树,请你返回满足以下条件的所有节点的值之和:

该节点的祖父节点的值为偶数。(一个节点的祖父节点是指该节点的父节点的父节点。)
如果不存在祖父节点值为偶数的节点,那么返回 0 。

示例:

在这里插入图片描述

输入:root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
输出:18
解释:图中红色节点的祖父节点的值为偶数,蓝色节点为这些红色节点的祖父节点。

提示:

树中节点的数目在 1 到 10^4 之间。
每个节点的值在 1 到 100 之间。

法一:直接递归模拟即可:

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int sumEvenGrandparent(TreeNode* root) {int ans = 0;findAns(root, false, false, ans);return ans;}private:void findAns(TreeNode *node, bool isEvenFather, bool isEvenGrandFather, int &ans){if (node == nullptr){return;}if (isEvenGrandFather){ans += node->val;}findAns(node->left, !(node->val & 1), isEvenFather, ans);findAns(node->right, !(node->val & 1), isEvenFather, ans);}
};

如果树中有n个节点,此算法时间复杂度为O(n),空间复杂度为O(logn)。

法二:广度优先搜索,每遍历到一个偶数节点,将其孙子节点的值加上:

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int sumEvenGrandparent(TreeNode* root) {queue<TreeNode *> q;q.push(root);int ans = 0;while (!q.empty()){TreeNode *node = q.front();q.pop();if (!(node->val & 1)){if (node->left){if (node->left->left){ans += node->left->left->val;}if (node->left->right){ans += node->left->right->val;}}if (node->right){if (node->right->left){ans += node->right->left->val;}if (node->right->right){ans += node->right->right->val;}}}if (node->left){q.push(node->left);}if (node->right){q.push(node->right);}}return ans;}
};

如果树中有n个节点,此算法时间复杂度为O(n),空间复杂度为O(logn)。

相关文章:

LeetCode 1315.祖父节点值为偶数的节点和

给你一棵二叉树&#xff0c;请你返回满足以下条件的所有节点的值之和&#xff1a; 该节点的祖父节点的值为偶数。&#xff08;一个节点的祖父节点是指该节点的父节点的父节点。&#xff09; 如果不存在祖父节点值为偶数的节点&#xff0c;那么返回 0 。 示例&#xff1a; 输入…...

C语言分支和循环总结

文章目录 概要结构介绍不同结构的语句简单运用小结 概要 C语言中分为三种结构&#xff1a;顺序结构&#xff0c;选择结构&#xff0c;循环结构 结构介绍 顺序结构就是从上到下&#xff0c;从左到右等等&#xff1b;选择结构可以想象是Y字路口就是到了一个地方会有不同的道路…...

【Echarts】曲线图上方显示数字以及自定义值,标题和副标题居中,鼠标上显示信息以及自定义信息

欢迎来到《小5讲堂》 大家好&#xff0c;我是全栈小5。 这是《前端》系列文章&#xff0c;每篇文章将以博主理解的角度展开讲解&#xff0c; 特别是针对知识点的概念进行叙说&#xff0c;大部分文章将会对这些概念进行实际例子验证&#xff0c;以此达到加深对知识点的理解和掌握…...

双环PID控制详细讲解

参考博客&#xff1a; &#xff08;1&#xff09;PID双环控制&#xff08;速度环和位置环&#xff09; &#xff08;2&#xff09;PID控制&#xff08;四&#xff09;&#xff08;单环与双环PID&#xff09; &#xff08;3&#xff09;内外双环pid算法 0 单环PID 目标位置→系…...

深入解析Java内存模型

一、背景 并发编程本质问题是&#xff1a;CPU、内存以及IO三者之间的速度差异。CPU速度快于内存、内存访问速度又远远快于IO&#xff0c;根据木桶理论&#xff0c;程序性能取决于最慢的操作&#xff0c;即IO操作。这样会出现CPU和内存交互时&#xff0c;CPU性能无法被充分利用…...

python使用国内镜像源

使用格式 格式为&#xff1a;pip install 库名 -i 镜像地址&#xff08;注意空格的存在&#xff09; pip install pandas -i https://pypi.tuna.tsinghua.edu.cn/simple 推荐的镜像源&#xff1a; 清华大学&#xff08;推荐&#xff09;&#xff1a;https://pypi.tuna.tsing…...

【动态规划】代码随想录算法训练营第四十六天 |139.单词拆分,关于多重背包,你该了解这些! ,背包问题总结篇!(待补充)

139.单词拆分 1、题目链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 2、文章讲解&#xff1a;代码随想录 3、题目&#xff1a; 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict&#xff0c;判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词…...

WordPress建站入门教程:如何选择和设置固定链接结构?

我们成功搭建好WordPress网站后&#xff0c;发布的文章对应的URL地址默认是使用“日期和名称型”&#xff0c;即是网站域名跟着的是年月日&#xff0c;最后是文章标题&#xff0c;如http://www.yigujin.com/2024/03/06/免费响应式WordPress博客主题JianYue/ 为了让我们的文章U…...

一款好用的AI工具——边界AICHAT(三)

目录 3.23、文档生成PPT演示3.24、AI文档翻译3.25、AI翻译3.26、论文模式3.27、文章批改3.28、文章纠正3.29、写作助手3.30、文言文翻译3.31、日报周报月报生成器3.32、OCR-DOC办公文档识别3.33、AI真人语音合成3.34、录音音频总结3.35、域方模型市场3.36、模型创建3.37、社区交…...

编程示例: 矩阵的多项式计算以javascript语言为例

编程示例: 矩阵的多项式计算以javascript语言为例 国防工业出版社的《矩阵理论》一书中第一章第8个习题 试计算2*A^8-3*A^5A^4A^2-4I A[[1,0,2],[0,-1,1],[0,1,0]] 代码如下 <html> <head> <title> 矩阵乘法 </title> <script srcset.js ><…...

project generator 简单使用

文章目录 1 progen 资源2 使用简介2.1 安装2.2 添加 target&#xff08;可选&#xff09;2.3 替换 CMake 模板&#xff08;可选&#xff09;2.4 创建 progen 项目 3 总结 1 progen 资源 0&#xff09;简介&#xff1a;progen&#xff08;project-generator&#xff0c;项目生成…...

C语言 —— 图形打印

题目1&#xff1a; 思路&#xff1a; 如果我们要打印一个实心正方形&#xff0c;其实就是一个二维数组&#xff0c;i控制行&#xff0c;j控制列&#xff0c;行列不需要控制&#xff0c;arr[i][j]直接打印星号即可。 对于空心正方形&#xff0c;我们只需要控制行和列的条件&…...

Python基础学习(11)常用模块

文章目录 一、time二、random三、os四、sys五、json补充1&#xff1a;JSON字符串补充2&#xff1a;JSON字符串和字典的区别 六、hashlib Python基础学习(1)基本知识 Python基础学习(2)序列类型方法与数据类型转换 Python基础学习(3)进阶字符串(格式化输出) Python基础学习(4)散…...

嵌入式学习37-TCP并发模型

TCP并发模型: 1.TCP多线程模型: 缺点: 1.创建线程会带来 资源开销 2.能够实现的 并发量 比较有限 2.IO模型: 1.阻塞IO: 没有…...

C语言字符函数和字符串函数

前言 今天这篇博客咱们一起来认识一些特殊的函数&#xff0c;在编程的过程中&#xff0c;我们经常要处理字符和字符串&#xff0c;为了方便字符和字符串&#xff0c;C语言提供了一些库函数&#xff0c;让我们一起看看这些函数都有什么功能吧&#xff01;&#xff01;&#xff0…...

Go语言必知必会100问题-22 空切片与nil切片有区别吗?

空切片与nil切片有区别吗&#xff1f; 很多开发人员经常混淆nil切片和空切片,不清楚什么时候使用空切片什么时候使用nil&#xff0c;而有些库函数又对这两者使用进行了区分。下面先来看看它们的定义。 空切片是length为0的切片当切片等于nil时为nil切片 下面是几种不同空切片…...

【C++进阶】C++多态概念详解

C多态概念详解 一&#xff0c;多态概念二&#xff0c;多态的定义2.1 多态构成的条件2.2 什么是虚函数2.3 虚函数的重写2.3.1 虚函数重写的特例2.3.2 override和final 2.4 重载和重写&#xff08;覆盖&#xff09;和重定义&#xff08;隐藏&#xff09;的区别 三&#xff0c;抽象…...

Python 导入Excel三维坐标数据 生成三维曲面地形图(面) 2、线条平滑曲面但有间隔

环境和包: 环境 python:python-3.12.0-amd64包: matplotlib 3.8.2 pandas 2.1.4 openpyxl 3.1.2 scipy 1.12.0 代码: import pandas as pd import matplotlib.pyplot as plt from mpl_toolkits.mplot3d import Axes3D from scipy.interpolate import griddata imp…...

前端精准测试调用链路分析

精准测试在评估需求的测试范围时&#xff0c;需要评估一下代码的影响范围&#xff0c;这个范围有两部分&#xff1a;一是需求直接修改的代码&#xff1b;二是修改代码影响到的功能模块。代码影响到的功能一般是通过调用链路分析来实现的&#xff0c;java和kotlin代码可以由java…...

Objective-C blocks 概要

1.block的使用 1.1什么是block&#xff1f; Blocks是C语言的扩充功能&#xff1a;带有自动变量&#xff08;局部变量&#xff09;的匿名函数。 “带有自动变量”在Blocks中表现为“截取自动变量" “匿名函数”就是“不带名称的函数” 块&#xff0c;封装了函数调用及调用…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

站群服务器的应用场景都有哪些?

站群服务器主要是为了多个网站的托管和管理所设计的&#xff0c;可以通过集中管理和高效资源的分配&#xff0c;来支持多个独立的网站同时运行&#xff0c;让每一个网站都可以分配到独立的IP地址&#xff0c;避免出现IP关联的风险&#xff0c;用户还可以通过控制面板进行管理功…...