当前位置: 首页 > 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;封装了函数调用及调用…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

6个月Python学习计划 Day 16 - 面向对象编程(OOP)基础

第三周 Day 3 &#x1f3af; 今日目标 理解类&#xff08;class&#xff09;和对象&#xff08;object&#xff09;的关系学会定义类的属性、方法和构造函数&#xff08;init&#xff09;掌握对象的创建与使用初识封装、继承和多态的基本概念&#xff08;预告&#xff09; &a…...

多元隐函数 偏导公式

我们来推导隐函数 z z ( x , y ) z z(x, y) zz(x,y) 的偏导公式&#xff0c;给定一个隐函数关系&#xff1a; F ( x , y , z ( x , y ) ) 0 F(x, y, z(x, y)) 0 F(x,y,z(x,y))0 &#x1f9e0; 目标&#xff1a; 求 ∂ z ∂ x \frac{\partial z}{\partial x} ∂x∂z​、 …...

TJCTF 2025

还以为是天津的。这个比较容易&#xff0c;虽然绕了点弯&#xff0c;可还是把CP AK了&#xff0c;不过我会的别人也会&#xff0c;还是没啥名次。记录一下吧。 Crypto bacon-bits with open(flag.txt) as f: flag f.read().strip() with open(text.txt) as t: text t.read…...

PydanticAI快速入门示例

参考链接&#xff1a;https://ai.pydantic.dev/#why-use-pydanticai 示例代码 from pydantic_ai import Agent from pydantic_ai.models.openai import OpenAIModel from pydantic_ai.providers.openai import OpenAIProvider# 配置使用阿里云通义千问模型 model OpenAIMode…...