_15LeetCode代码随想录算法训练营第十五天-C++二叉树

news/2024/5/6 16:50:32/文章来源:https://blog.csdn.net/weixin_44410704/article/details/128438254

_15LeetCode代码随想录算法训练营第十五天-C++二叉树

题目列表

  • 110.平衡二叉树
  • 257.二叉树的所有路径
  • 404.左叶子之和

110.平衡二叉树

题目

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

代码

/** @lc app=leetcode.cn id=110 lang=cpp** [110] 平衡二叉树*/// @lc code=start
/*** 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 getHeight(TreeNode* node){if(node == nullptr)return 0;int leftH = getHeight(node->left);int rightH = getHeight(node->right);//如果左子树不平衡，则返回-1if(leftH == -1)return -1;//如果右子树不平衡，则返回-1if(rightH == -1)return -1;//如果左右子树的高度差大于1，则返回-1//否则，返回当前node的高度if(abs(leftH - rightH) > 1)return -1;elsereturn 1 + max(leftH, rightH);        }bool isBalanced(TreeNode* root) {if(getHeight(root) == -1)return false;elsereturn true;}
};
// @lc code=end

257.二叉树的所有路径

题目

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

思路

前序遍历，有回溯。

有递归，就有回溯。
在这里插入图片描述

代码

递归代码

思路清晰代码

/** @lc app=leetcode.cn id=257 lang=cpp** [257] 二叉树的所有路径*/// @lc code=start
/*** 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:void traverse(TreeNode* node, vector<int>& path, vector<string>& res){//中path.push_back(node->val);//当node的左孩子和右孩子都为空时，说明遍历到了叶子节点if(node->left == nullptr && node->right == nullptr){//此时就要将path加入res中//先将path转换为stringstring data;for(int i = 0; i < path.size() - 1; i++){data += to_string(path[i]);data += "->";}//处理最后一个节点data += to_string(path[path.size() - 1]);res.push_back(data);return;}//左if(node->left != nullptr){traverse(node->left, path, res);//有递归path.pop_back();//有回溯}//右if(node->right != nullptr){traverse(node->right, path, res);//有递归path.pop_back();//有回溯}}vector<string> binaryTreePaths(TreeNode* root) {vector<int> path;vector<string> res;if(root == nullptr)return res;traverse(root, path, res);return res;}
};
// @lc code=end

经典代码

/** @lc app=leetcode.cn id=257 lang=cpp** [257] 二叉树的所有路径*/// @lc code=start
/*** 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 {
private://回溯是通过函数的实参path实现的，此参数不是引用不是指针，因此当递归调用时，使用的是临时变量，//在本递归中，改变path的值不会改变上一层递归中path的值，由此实现了回溯。void traversal(TreeNode* cur, string path, vector<string>& result) {path += to_string(cur->val); // 中if (cur->left == NULL && cur->right == NULL) {result.push_back(path);return;}if (cur->left) traversal(cur->left, path + "->", result); // 左if (cur->right) traversal(cur->right, path + "->", result); // 右}
public:vector<string> binaryTreePaths(TreeNode* root) {vector<string> result;string path;if (root == NULL) return result;traversal(root, path, result);return result;}
};
// @lc code=end

非递归代码

/** @lc app=leetcode.cn id=257 lang=cpp** [257] 二叉树的所有路径*/// @lc code=start
/*** 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:vector<string> binaryTreePaths(TreeNode* root) {vector<string> res;//此栈存储TreeNode*stack<TreeNode*> stTree;//此栈存储路径stack<string> stRes;if(root == nullptr)return res;stTree.push(root);stRes.push(to_string(root->val));while(!stTree.empty()){TreeNode* node = stTree.top();stTree.pop();string path = stRes.top();stRes.pop();if(node->left == nullptr && node->right == nullptr)res.push_back(path);if(node->left != nullptr){stTree.push(node->left);stRes.push(path + "->" + to_string(node->left->val));}if(node->right != nullptr){stTree.push(node->right);stRes.push(path + "->" + to_string(node->right->val)); }}return res;}
};
// @lc code=end

404.左叶子之和

题目

给定二叉树的根节点 root ，返回所有左叶子之和。
在这里插入图片描述

整体思路

左叶子的明确定义：节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点
在这里插入图片描述

代码

递归代码

/** @lc app=leetcode.cn id=404 lang=cpp** [404] 左叶子之和*/// @lc code=start
/*** 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 sumOfLeftLeaves(TreeNode* root) {if(root == nullptr)return 0;if(root->left == nullptr && root->right == nullptr)return 0;//遍历左子树int leftValue = sumOfLeftLeaves(root->left);if(root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr)leftValue = root->left->val;//遍历右子树int rightValue = sumOfLeftLeaves(root->right);return leftValue + rightValue;}
};
// @lc code=end

非递归代码

/** @lc app=leetcode.cn id=404 lang=cpp** [404] 左叶子之和*/// @lc code=start
/*** 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 sumOfLeftLeaves(TreeNode* root) {queue<TreeNode*> que;int res = 0;if(root != nullptr)que.push(root);while(!que.empty()){TreeNode* node = que.front();que.pop();if(node->left != nullptr && node->left->left == nullptr && node->left->right == nullptr)res += node->left->val;if(node->left != nullptr)que.push(node->left);if(node->right != nullptr)que.push(node->right);}return res;}
};
// @lc code=end

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

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

相关文章

SpringBoot-2 读取properties；自动加载127个类原理总结；全部加载，按需配置

SpringBoot-2 读取properties；自动加载127个类原理总结；全部加载，按需配置

读取properties 方式一&#xff1a;非配置类填写&#xff1a;ComponentConfigurationProperties 1)建立bean&#xff1a; /只有在容器中的组件才拥有springboot提供的强大功能 Component ConfigurationProperties(prefix "mycar") public class Car {private Stri…
阅读更多...
NetSuite Decode函数

NetSuite Decode函数

昨天是平安夜&#xff0c;小家伙仍然为圣诞老人的到来准备了礼物&#xff0c;这是他的传统。每年为了感谢圣诞老人和驯鹿的到来&#xff0c;他都会准备上点心、水果。今年&#xff0c;他认为驯鹿可能需要电力&#xff0c;所以准备了电池给它们享用。 真希望天真一直伴随他的成长…
阅读更多...
互联网技术不再是统领，当下正在发生着一场深刻的变革

互联网技术不再是统领，当下正在发生着一场深刻的变革

拥抱实体经济&#xff0c;绝对是当下互联网玩家们的首要选择。无论是头部的互联网企业来讲&#xff0c;还是新生的互联网玩家而言&#xff0c;它们都不约而同地将关注的焦点聚焦在了这样一个方向上。 　　透过这一点&#xff0c;我们可以非常明显地感受到&#xff0c;一个全新的…
阅读更多...
蓝桥杯备赛Day4——多维数组

蓝桥杯备赛Day4——多维数组

二维数组初始化 p[[0 for i in range(5)] for j in range(2)] #法一 p[[0]*5 for j in range(2)] #法二 s[[1,2,3],[4,5,6]] print(s) for i in range(2):for j in range(3):print(s[i][j],end ) 三维数组初始化 a[[[0 for _ in range(2)] for __ in…
阅读更多...
CSDN每日一练最长递增的区间长度 C语言

CSDN每日一练最长递增的区间长度 C语言

题目名称&#xff1a;最长递增的区间长度 时间限制&#xff1a;1000ms 内存限制&#xff1a;256M 题目描述 给一个无序数组&#xff0c;求最长递增的区间长度。如&#xff1a;[5,2,3,8,1,9] 最长区间 2,3,8 长度为 3 &#xff08;注意&#xff1a;测试用例仅做参考&#xff0c;…
阅读更多...
windows@网络防火墙@软件联网控制

windows@网络防火墙@软件联网控制

文章目录ref打开防火墙控制面板常用部分限制某个软件联网文档参考具体操作取消控制/禁用第三方软件控制ref (Windows) 创建出站端口规则 | Microsoft LearnWindows Defender Firewall with Advanced Security (Windows) | Microsoft Learn组策略 Windows) 高级安全性的 Window…
阅读更多...
二叉树经典算法题目

二叉树经典算法题目

1.二叉树的前中后序遍历&#xff08;简单&#xff09; 省略 2.二叉树的深度(简单) 输入一棵二叉树的根节点&#xff0c;求该树的深度。从根节点到叶节点依次经过的节点&#xff08;含根、叶节点&#xff09;形成树的一条路径&#xff0c;最长路径的长度为树的深度。 例如&a…
阅读更多...
VS coda C++、python运行与Dbug配置

VS coda C++、python运行与Dbug配置

首先新建终端 一次性使用C方法 检查C编译器是否存在 which g可见位置存在于&#xff1a;/usr/bin/g 一次性命令格式&#xff1a; 使用json配置文件 运行C方法&#xff08;推荐&#xff09;&#xff1a; 根据你查找的g的位置来决定 使用配置好的tasks.json&#xff08;C的…
阅读更多...
Java window多环境配置

Java window多环境配置

目录JDK版本下载配置内容描述创建JAVA_HOME在Path配置版本切换效果JDK版本下载 Java8 Download address 这个是Java8 的下载地址&#xff0c;下载是要登录的&#xff0c;自己花费一点时间去注册。如果想要下载其它版本的JDK&#xff0c;请看下面的图&#xff0c;然后你就可以看…
阅读更多...
SSD_学习笔记记录

SSD_学习笔记记录

one-steage VGG16模型的修改 VGG16的模型输出&#xff0c;其中224.。。为特征图的大小。 SSD模型中对VGG网络的修改&#xff1a; SSD模型是对VGG中的第四个卷积块中的最后一个Conv2d进行第一个输出&#xff0c;在这里简称为Conv4-3。以及第五个卷积块中的最后一个Conv2d进行…
阅读更多...
前端开发：Vue封装通过API调用的组件的方法

前端开发：Vue封装通过API调用的组件的方法

前言 在前端开发中&#xff0c;关于Vue的使用相比大家并不陌生&#xff0c;而且Vue框架的优势也是其他框架所不能比的&#xff0c;尤其是Vue的封装思想更是堪称一绝&#xff0c;还有就是组件化的运用实践过程也是亮点。所以关于Vue框架的使用想必看官都不陌生&#xff0c;而且常…
阅读更多...
干货 | 关于PCB中的“平衡铜”，一文全部说明白

干货 | 关于PCB中的“平衡铜”，一文全部说明白

平衡铜是PCB设计的一个重要环节&#xff0c;对PCB上闲置的空间用铜箔进行填充&#xff0c;一般将其设置为地平面。 平衡铜的意义在于&#xff1a; 对信号来说&#xff0c;提供更好的返回路径&#xff0c;提高抗干扰能力&#xff1b;对电源来说&#xff0c;降低阻抗&#xff0c;…
阅读更多...
8 NP完全性理论

8 NP完全性理论

8 NP完全性理论 p问题 NP问题 NP完全问题 NPC(complete ) NP难问题NP-hard p问题 是一类能够用**(确定的)算法**在多项式时间内求解的可判定问题 ●这种问题类型也称为多项式类型 NP问题 是一类能够用不确定算法在多项式时间内求解的可判定问题 在确定性计算模型下多项式时…
阅读更多...
Web前端105天-day64-HTML5_CORE

Web前端105天-day64-HTML5_CORE

HTML5CORE04 目录 前言 一、复习 二、WebSocket 三、服务器搭建 四、聊天室 五、defineProperty 5.1.初识defineProperty 5.2.配置多个属性 5.3.可配置 5.4.赋值监听 5.5.练习 5.6.计算属性 总结 前言 HTML5CORE04学习开始 一、复习 SVG: 利用HTML的 DOM 来绘制图…
阅读更多...
juc-4-synchronized原理

juc-4-synchronized原理

目录 1、synchronized 作用于静态方法 总结 ​编辑 案例 静态成员变量 (synchronized锁非静态方法) 案例 静态成员变量 (synchronized锁静态方法 或 直接锁类) 2、监视器锁(monitor) 2.1 synchronized怎么实现的线程安全呢&#xff1f; 3、JDK6 synchronized 的优化 3.1 C…
阅读更多...
6.s081 学习实验记录（二）xv6 and unix utilities

6.s081 学习实验记录（二）xv6 and unix utilities

文章目录一、boot xv6二、sleep三、pingpong四、primes五、find六、xargs该实验主要用来熟悉xv6以及其系统调用 一、boot xv6 实验目的&#xff1a; 启动xv6系统&#xff0c;并使用提供的命令ls&#xff0c;列出系统所有的文件ctrl p&#xff0c;打印当前运行的进程ctrl a…
阅读更多...
IP地址分类及范围详解

IP地址分类及范围详解

IP地址分为公网IP地址&#xff08;合法IP地址&#xff09;和私有IP地址 公网IP地址主要应用于Internet上的主机访问&#xff0c;而私有IP地址应用于局域网中计算机的相互通信。 IP地址的表示形式&#xff1a;分为二进制表示和点分十进制表示。现在使用的IP地址长度均为32位/4个…
阅读更多...
玩转GPT--在线文本生成项目[可入坑~科普系列]

玩转GPT--在线文本生成项目[可入坑~科普系列]

文章目录前言效果页面说明文字个数top_KTop_Ptemperature聊天上下文关联记忆项目部署获取项目获取模型运行彩蛋总结前言 没办法&#xff0c;最近ChatGPT杀疯了&#xff0c;没忍住&#xff0c;还是想look&#xff0c;look。没办法&#xff0c;哪个帅小伙能够忍受的了一个可以和…
阅读更多...
红中私教：计网那点事（1）

红中私教：计网那点事（1）

前言 &#x1f340;作者简介&#xff1a;被吉师散养、喜欢前端、学过后端、练过CTF、玩过DOS、不喜欢java的不知名学生。 &#x1f341;个人主页&#xff1a;红中 &#x1f342;专栏地址&#xff1a;网安专栏 光明神已陨落&#xff0c;现在 由计网引领我 破戒了&#xff0c;本来…
阅读更多...
力扣刷题笔记day10（树的子结构+二叉树镜像+对称的二叉树）

力扣刷题笔记day10（树的子结构+二叉树镜像+对称的二叉树）

文章目录树的子结构题目思路代码二叉树镜像题目思路代码对称的二叉树题目思路代码树的子结构 输入两棵二叉树A和B&#xff0c;判断B是不是A的子结构。(约定空树不是任意一个树的子结构) B是A的子结构&#xff0c; 即 A中有出现和B相同的结构和节点值。 题目 思路 dfs(A, B) …
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站 广利置业