【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);}}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/380045.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

三、初识C语言(3)

1.操作符 &#xff08;1&#xff09;算术操作符 - * / % 商 余&#xff08;取模&#xff09; 小算法&#xff1a; 若a<b&#xff0c;则a%b a 若a%b c&#xff0c;则0 < c < b-1 若两个int 类型数相除&#xff0c;结果有小数会被舍弃。 保留小数…

阿里云 申请免费ssl 证书

1控制台--数字证书管理服务 2 创建所需域名证书

下载安装VSCode并添加插件作为仓颉编程入门编辑器

VSCode下载地址&#xff1a;下载 Visual Studio Code - Mac、Linux、Windows 插件下载&#xff1a;GitCode - 全球开发者的开源社区,开源代码托管平台 仓颉社区中下载解压 cangjie.vsix 插件 打开VSCode 按 Ctrl Shift X 弹出下图 按照上图步骤依次点击选中我们下…

openstack设置IP直接登录,不需要加dashboard后缀

openstack 实验环境&#xff0c;openstack-t版&#xff0c;centos2009 修改配置文件 [rootcontroller ~]# vim /WEBROOT /etc/openstack-dashboard/local_settings #将dashboard去掉 WEBROOT /dashboard/ #改为 WEBROOT /[rootcontroller ~]# vim /etc/httpd/conf.d/openst…

vscode搭建PyQt + Quick开发环境

VScode搭建PyQt Quick开发环境 目录 环境准备 &#x1f514;安装必要的Python包 &#x1f514;&#x1f50e; PyQt5和PySide2的区别&#x1f4be; 安装PyQt5&#x1f4be; 安装PySide2 配置VScode &#x1f514;&#x1f4bb; 安装扩展 代码示例 &#x1f514;✔ Python调用Qt…

分布式 I/O 系统Modbus TCP 耦合器BL200

BL200 耦合器是一个数据采集和控制系统&#xff0c;基于强大的 32 位微处理器设计&#xff0c;采用 Linux 操作系统&#xff0c;可以快速接入现场 PLC、SCADA 以及 ERP 系统&#xff0c; 内置逻辑控制、边缘计算应用&#xff0c;支持标准 Modbus TCP 服务器通讯&#xff0c;以太…

光耦合器技术的实际应用

光耦合器也称为光隔离器&#xff0c;是现代电子产品中的关键组件&#xff0c;可确保电路不同部分之间的信号完整性和隔离。它们使用光来传输电信号&#xff0c;提供电气隔离和抗噪性。 结构和功能 光耦合器通常由以下部分组成&#xff1a; 1.LED&#xff08;发光二极管&#…

pytorch学习(七)torchvision.datasets的使用

网络上已经有公开的数据集&#xff0c;并且这些数据集被整合到了torchvision.datasets中&#xff0c;使用自带的函数可以直接下载。 1.数据集 具体有哪些数据可直接用torchvision.datasets加载呢&#xff1f;可以查看这个网址&#xff1a; datasets官网&#xff1a;Datasets…

二叉树基础及实现(一)

目录&#xff1a; 一. 树的基本概念 二. 二叉树概念及特性 三. 二叉树的基本操作 一. 树的基本概念&#xff1a; 1 概念 &#xff1a; 树是一种非线性的数据结构&#xff0c;它是由n&#xff08;n>0 &#xff09;个有限结点组成一个具有层次关系的集合。 把它叫做树是因…

debian 更新源

前言 实现一键替换在线源 一键更新源 Debian 全球镜像站以下支持现有debian 11 12 echo "Delete the default source" rm -rf /etc/apt/sources.listecho "Build a new source" cat <<EOF>>/etc/apt/sources.list.d/debian.sources Types:…

将iPad 作为Windows电脑副屏的几种方法(二)

将iPad 作为Windows电脑副屏的几种方法&#xff08;二&#xff09; 1. 前言2. EV 扩展屏2.1 概述2.2 下载、安装、连接教程2.3 遇到的问题和解决方法2.3.1 平板连接不上电脑 3. Twomon SE3.1 概述3.2 下载安装教程 4. 多屏中心&#xff08;GlideX&#xff09;4.1 概述4.2 下载安…

pdf怎么压缩的小一点?PDF压缩变小的6种方法(2024全新)

pdf怎么压缩的小一点&#xff1f;首先&#xff0c;PDF文件可以进行压缩。职场文档传阅还是比较建议PDF压缩&#xff0c;PDF文件可以无障碍访问&#xff0c;保持原始文本、图像和表格&#xff0c;无需担心展示效果差异等等优势&#xff0c;成为我们日常工作中不可或缺的一部分。…

AGI 之 【Hugging Face】 的【零样本和少样本学习】之三 [无标注数据] 的简单整理

AGI 之 【Hugging Face】 的【零样本和少样本学习】之三 [无标注数据] 的简单整理 目录 AGI 之 【Hugging Face】 的【零样本和少样本学习】之三 [无标注数据] 的简单整理 一、简单介绍 二、零样本学习 (Zero-shot Learning) 和少样本学习 (Few-shot Learning) 1、零样本学…

MF173:将多个工作表转换成PDF文件

我给VBA的定义&#xff1a;VBA是个人小型自动化处理的有效工具。利用好了&#xff0c;可以大大提高自己的工作效率&#xff0c;而且可以提高数据的准确度。“VBA语言専攻”提供的教程一共九套&#xff0c;分为初级、中级、高级三大部分&#xff0c;教程是对VBA的系统讲解&#…

python多幅图自适应紧致二维排放

有时可视化会要同时放多幅图&#xff0c;如分割的原图、label、pseudo-label 和 prediction。当图很多&#xff0c;简单地排成一行可能会太长&#xff0c;不便观看。考虑将图排成二维网格&#xff08;grid&#xff09;展示&#xff0c;且为方便看&#xff0c;考虑让网格尽可能「…

word 设置多级混合标题自动更新

目录预览 一、问题描述二、原因分析三、解决方案四、参考链接 一、问题描述 有没有体会过多级标题&#xff0c;怎么设置都不听使唤的情况&#xff1f; 我想要的格式是&#xff1a; 二、原因分析 多级标题中发现&#xff0c;输入编号格式这里有个数字没有底纹,是了&#xff0…

【第4章】Spring Cloud之Nacos单机模式支持mysql

文章目录 前言一、初始化1. 初始化数据库2. 修改配置文件 二、效果1. 重新启动2. 新增用户 总结 前言 在0.7版本之前&#xff0c;在单机模式时nacos使用嵌入式数据库实现数据的存储&#xff0c;不方便观察数据存储的基本情况。0.7版本增加了支持mysql数据源能力&#xff0c;具…

PhantomJs将html生成img|pdf

PhantomJS PhantomJS是一个可编程的无头浏览器&#xff0c;‌它基于WebKit内核&#xff0c;‌通过JavaScript API进行脚本化操作&#xff0c;它对各种web标准有快速和原生化的支持&#xff0c;包括DOM处理、CSS选择器、JSON、Canvas和SVG。‌无头浏览器指的是一个完整的浏览器内…

顶着关税也要出海,蔚来如何找到未来?

“买得杏花&#xff0c;十载归来方始坼。” 十年的时间&#xff0c;足以见证每一个市场与品牌的白云苍狗、沧海桑田。 而2024年&#xff0c;也是蔚来成立的第十年。这十年里&#xff0c;中国的新能源车的渗透率从0.32%提高到了31.6%&#xff0c;蔚来从一家初创车企成长为如今…

设计模式——模版方法和策略模式

前言 作为一名资深CV工程师&#xff0c;学会为自己减少工作量乃重中之重。但只是一味地CV&#xff0c;只会因为劣质代码而让自己的工作量加倍&#xff0c;为了将来不被繁重的维护工作而打扰自己的休息日&#xff0c;为了更好的节能&#xff0c;学习设计模式&#xff0c;刻不容缓…