【LeetCode】day15:110 - 平衡二叉树, 257 - 二叉树的所有路径, 404 - 左叶子之和, 222 - 完全二叉树的节点个数
LeetCode 代码随想录跟练 Day15
- 110.平衡二叉树
- 257.二叉树的所有路径
- 404.左叶子之和
- 222.完全二叉树的节点个数
110.平衡二叉树
题目描述:
给定一个二叉树,判断它是否是 平衡二叉树
平衡二叉树的定义是,对于树中的每个节点,其左右子树的高度差不超过1。思路使用递归,对比左子树和右子树的高度差是否超过1,若超过1则当前节点返回-1作为标示,否则返回当前节点的最大深度。代码如下:
class Solution {
private:int traverse(TreeNode* root) {if (root == nullptr) return 0;int leftHeight = traverse(root->left);int rightHeight = traverse(root->right);if (leftHeight == -1 || rightHeight == -1) {return -1;}if (leftHeight - rightHeight > 1 || leftHeight - rightHeight < -1) {return -1;}return max(leftHeight, rightHeight) + 1;}public:bool isBalanced(TreeNode* root) {int height = traverse(root);if (height == -1) return false;return true;}
};
257.二叉树的所有路径
题目描述:
给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
主要思路为对树进行遍历并将遍历时的当前路径记录,并在到达叶子节点后将当前路径添加到结果中。同时在遍历过程中需要对路径的状态实时进行回溯,比如从当前节点退出,上一个节点的路径中就不应再保留当前节点的信息。这里使用字符串值传递方式,可以非显式的实现回溯。代码如下:
class Solution {
private:void traverse(TreeNode* root, string path, vector<string>& paths) {if (root == nullptr) return;if (!path.empty()) path += "->";path += to_string(root->val);if (!root->left && !root->right) {paths.push_back(path);return;}traverse(root->left, path, paths);traverse(root->right, path, paths);}public:vector<string> binaryTreePaths(TreeNode* root) {vector<string> res;if (root == nullptr) return res;traverse(root, "", res);return res;}
};
另外使用迭代法进行遍历时,原理相同,在push节点进入记录节点的stack时同时将当前路径同时push进入记录路径的stack中,这样在每次循环获取当前节点时获取到的路径是对应的。注意在分别对左右节点的路径修改时,由于存在需要在处理前一个之后继续处理后一个的情况(左右节点都不为nullptr),所以不能修改path变量而是应该通过临时变量记录路径并入栈。代码如下:
class Solution {
public:vector<string> binaryTreePaths(TreeNode* root) {vector<string> res;if (root == nullptr) return res;stack<TreeNode*> nodeStk;stack<string> pathStk;nodeStk.push(root);pathStk.push(to_string(root->val));while (!nodeStk.empty()) {TreeNode* cur = nodeStk.top(); nodeStk.pop();string path = pathStk.top(); pathStk.pop();if (!cur->left && !cur->right) {res.push_back(path);continue;}if (cur->left) {nodeStk.push(cur->left);pathStk.push(path + "->" + to_string(cur->left->val));}if (cur->right) {nodeStk.push(cur->right);pathStk.push(path + "->" + to_string(cur->right->val));}}return res;}
};
404.左叶子之和
题目描述:
给定二叉树的根节点 root ,返回所有左叶子之和。
示例 1:
输入: root = [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24
示例 2:
输入: root = [1]
输出: 0
在遍历时使用isLeft的bool变量标示当前节点是否是上一个状态的左节点,在确认叶子节点值时同时需要确保该bool变量为true,其余均为遍历框架。代码如下:
class Solution {
private:int traverse(TreeNode* root, bool isLeft) {if (root == nullptr) return 0;if (!root->left && !root->right && isLeft) {return root->val;}int left = traverse(root->left, true);int right = traverse(root->right, false);return left + right;}public:int sumOfLeftLeaves(TreeNode* root) {return traverse(root, false);}
};
同理可以使用迭代法,通过确认左节点的方式:若左节点不为nullptr且为叶子节点,则记录结果,除此之外的所有都不算左叶子。代码如下:
class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {if (root == nullptr) return 0;stack<TreeNode*> stk;stk.push(root);int res = 0;while (!stk.empty()) {TreeNode* cur = stk.top(); stk.pop();// 若左节点不为nullptr且为叶子节点if (cur->left && !cur->left->left && !cur->left->right) {res += cur->left->val;}if (cur->left) stk.push(cur->left);if (cur->right) stk.push(cur->right);}return res;}
};
222.完全二叉树的节点个数
题目描述:
给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。
完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1 1 1~ 2 h 2^h 2h 个节点。
示例 1:
输入:root = [1,2,3,4,5,6]
输出:6
示例 2:
输入:root = []
输出:0
示例 3:
输入:root = [1]
输出:1
最简单的二叉树遍历计算节点数,这里使用层序遍历实现:
class Solution {
public:int countNodes(TreeNode* root) {if (root == nullptr) return 0;queue<TreeNode*> q;int res = 0;q.push(root);while (!q.empty()) {int size = q.size();res += size;while (size--) {TreeNode* cur = q.front(); q.pop();if (cur->left) q.push(cur->left);if (cur->right) q.push(cur->right);}}return res;}
};
由于题中所给为完全二叉树,可以根据其特性进行优化:完全二叉树的高度可以通过一直向左直到叶子节点确定、完全二叉树的节点树可以通过比较左右子树的高度来判断。
若左子树高度等于右子树,根据完全二叉树的性质可知左子树为满二叉树(完全二叉树的叶子节点从最左边开始,右子树高度相同则表示左边排满了);若高度不同相反则表示左子树不满,而右子树一定是高度小一行的满二叉树。代码如下:
class Solution {
private:int getHeight(TreeNode* node) {int res = 0;while (node) {++res;node = node->left;}return res;}public:int countNodes(TreeNode* root) {if (root == nullptr) return 0;int leftHeight = getHeight(root->left);int rightHeight = getHeight(root->right);if (leftHeight == rightHeight) {return (1 << leftHeight) + countNodes(root->right);} else {return (1 << rightHeight) + countNodes(root->left);}}
};
相关文章:
【LeetCode】day15:110 - 平衡二叉树, 257 - 二叉树的所有路径, 404 - 左叶子之和, 222 - 完全二叉树的节点个数
LeetCode 代码随想录跟练 Day15 110.平衡二叉树257.二叉树的所有路径404.左叶子之和222.完全二叉树的节点个数 110.平衡二叉树 题目描述: 给定一个二叉树,判断它是否是 平衡二叉树 平衡二叉树的定义是,对于树中的每个节点,其左右…...
【网络安全的神秘世界】Error:Archives directory /var/cache/apt/archives/partial is missing.
🌝博客主页:泥菩萨 💖专栏:Linux探索之旅 | 网络安全的神秘世界 | 专接本 | 每天学会一个渗透测试工具 ✨问题描述 在kali中想要安装beef-xss软件包时,发生如下报错: Error: Archives directory /var/cac…...
网络编程中的TCP和UDP
什么是TCP协议 TCP( Transmission control protocol )即传输控制协议,是一种面向连接、可靠的数据传输协议,它是为了在不可靠的互联网上提供可靠的端到端字节流而专门设计的一个传输协议。 面向连接 :数据传输之前客户端和服务器端必须建立连…...
基于python的时空地理加权回归(GTWR)模型
一、时空地理加权回归(GTWR)模型 时空地理加权回归(GTWR)模型是由美国科罗拉多州立大学的Andy Liaw、Stanley A. Fiel和Michael E. Bock于2008年提出的一种高级空间统计分析方法。它是在传统地理加权回归(GWR…...
什么是单例模式,有哪些应用?
目录 一、定义 二、应用场景 三、6种实现方式 1、懒汉式,线程不安全。 2、懒汉式,线程安全 3、双检锁/双重校验锁(DCL,即 double-checked locking) 4、静态内部类方式-------只适用于静态域 5、饿汉式 6、枚举…...
adb命令操作手机各种开关
打开iqoo手机热点设置 adb shell am start -n com.android.settings/com.android.settings.Settings$\VivoTetherSettingsActivity蓝牙模块 检查蓝牙状态的ADB命令 检查蓝牙开关状态 adb shell settings get global bluetooth_on开启和关闭蓝牙 使用Intent操作蓝牙…...
【分布式存储系统HDFS】架构和使用
分布式存储系统HDFS:架构和使用 目录 引言HDFS简介HDFS的架构 NameNodeDataNodeSecondary NameNode HDFS的工作原理 数据读写流程数据冗余与恢复 HDFS的安装和配置 环境准备HDFS安装步骤HDFS配置文件启动HDFS HDFS的使用 基本命令HDFS Shell操作Java API操作 HDFS…...
Linux 实验一Linux系统安装
一、实验日期与地址 1、实验日期:2024年 2 月28 日 2、实验地址:S1-504 二、实验目的 1、掌握VMware Workstation建立虚拟机 2、掌握虚拟机环境下安装Centos 7 三、实验环境 VMware Workstation、Centos 7 四、实验内容 1、安装VMware Workstat…...
【人工智能】深度剖析AI伦理:强化隐私防线,推动算法公平性的核心议题
文章目录 🍊1 人工智能兴起背后的伦理及道德风险1.1 算法偏见与歧视1.2 数据隐私侵权1.3 透明度受限1.4 决策失衡1.5 AI生成内容的危险性 🍊2 建构AIGC伦理观:实现人机共创的永续提升2.1 技术手段与伦理预防2.2 即时警告与紧急关停措施2.3 法…...
如何解决微服务下引起的 分布式事务问题
一、什么是分布式事务? 虽然叫分布式事务,但不是一定是分布式部署的服务之间才会产生分布式事务。不是在同一个服务或同一个数据库架构下,产生的事务,也就是分布式事务。 跨数据源的分布式事务 跨服务的分布式事务 二、解决方…...
牛客周赛50轮+cf955+abc363
D-小红的因式分解_牛客周赛 Round 50 (nowcoder.com) 思路: 巨蠢的题目,ax^2bxca1*a2*x^2(b1*a2b2*a1)xb1*b2,即: aa1*a2,ba1*b2a2*b1,cb1*b2 数据范围很小,直接暴力枚举吧(注意条件) 代码…...
【MySQL】:对库和表的基本操作方法
数据库使用的介绍 什么是SQL 学习数据库的使用——>基于 SQL编程语言 来对数据库进行操作 重点表述的是“需求”,期望得到什么结果。(至于结果是如何得到的,并不关键,都是数据库服务器在背后做好了) 重点表述的是…...
Library not found for -lstdc++.6.0.9
解决方案一 由于项目已经很多年了,前段时间更新了Xcode发现编译报错lstdc这个库很早以前就被舍弃了,但是一个项目的维护都随着解决bug堆砌出来的,这也导致了我们的项目走上了这条路。 比如 Library not found for -lstdc.6.0.9 报的错&#x…...
防火墙之双机热备篇
为什么要在防火墙上配置双机热备技术呢? 相信大家都知道,为了提高可靠性,避免单点故障 肯定有聪明的小伙伴会想到那为什么不直接多配置两台防火墙,然后再将他们进行线路冗余,不就完成备份了吗? 答案是不…...
终端里面ifconfig命令无法运行
在 Ubuntu 以及基于 Debian 的系统中,ifconfig 命令可能不会默认安装,因为自 Ubuntu 17.10 版本开始,系统默认使用 ip 命令作为网络配置的主要工具,而 ifconfig 命令则来自 net-tools 包,该包不再作为标准工具被包含在…...
掌握Python中的文件序列化:Json和Pickle模块解析
Python 文件操作与管理:Open函数、Json与Pickle、Os模块 在Python中,文件是一个重要的数据处理对象。无论是读取数据、保存数据还是进行数据处理,文件操作都是Python编程中不可或缺的一部分。本文将详细介绍Python中文件操作的几种常用方法&…...
WordPress 6.6 “Dorsey多尔西”发布
WordPress 6.6 “Dorsey多尔西”已经发布,它以传奇的美国大乐队领袖 Tommy Dorsey 名字命名。Dorsey 以其音调流畅的长号和作品而闻名,他的音乐以其情感深度和充满活力的能量吸引了观众。 当您探索 WordPress 6.6 的新功能和增强功能时,让您的…...
核函数支持向量机(Kernel SVM)
核函数支持向量机(Kernel SVM)是一种非常强大的分类器,能够在非线性数据集上实现良好的分类效果。以下是关于核函数支持向量机的详细数学模型理论知识推导、实施步骤与参数解读,以及两个多维数据实例(一个未优化模型&a…...
二分查找(折半查找)
这次不排序了,对排好序的数组做个查找吧 介绍 二分查找排序英文名为BinarySort,是一种效率较高的查找方法要求线性表必须采用顺序存储结构 基本思路 通过不断地将搜索范围缩小一半来找到目标元素: 1、假定数组为arr,需要查找的…...
arcgis紧凑型切片缓存(解决大范围切片,文件数量大的问题)
ArcGIS 切片缓存的紧凑型存储格式是一种优化的存储方式,用于提高切片缓存的存储效率和访问速度。紧凑型存储格式将多个切片文件合并为一个单一的 .bundle 文件,从而减少文件系统的开销和切片的加载时间。这类格式已经应用很久了,我记得2013我…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
Kafka入门-生产者
生产者 生产者发送流程: 延迟时间为0ms时,也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于:异步发送不需要等待结果,同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...

