LeetCode---二叉树
144/94/145. 二叉树的前、中、后序的递归遍历
以中序遍历为例,其余类似:
给定一个二叉树的根节点
root
,返回 它的 中序 遍历 。
代码示例:
/*** 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 traversal(TreeNode* cur,vector<int>& vec){if(cur == NULL) return;traversal(cur->left,vec);//左vec.push_back(cur->val);//中traversal(cur->right,vec);//右}vector<int> inorderTraversal(TreeNode* root) {vector<int> result;traversal(root,result);return result;}
};
总结:不同的遍历方式只需将前中后三行代码交换顺序即可
递归三要素:
确定递归函数的参数和返回值: 确定哪些参数是递归的过程中需要处理的,那么就在递归函数里加上这个参数, 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
确定终止条件: 写完了递归算法, 运行的时候,经常会遇到栈溢出的错误,就是没写终止条件或者终止条件写的不对,操作系统也是用一个栈的结构来保存每一层递归的信息,如果递归没有终止,操作系统的内存栈必然就会溢出。
确定单层递归的逻辑: 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
144/94/145. 二叉树的前、中、后序的非递归遍历(迭代)
1. 前序遍历和后续遍历:遍历节点和处理节点相同,可共用一套规则
2. 中序遍历:遍历节点和处理节点不相同
前序遍历:
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> result;if (root == NULL) return result;st.push(root);while (!st.empty()) {TreeNode* node = st.top(); // 中st.pop();result.push_back(node->val);if (node->right) st.push(node->right); // 右(空节点不入栈)if (node->left) st.push(node->left); // 左(空节点不入栈)}return result;}
};
后序遍历:
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> result;if (root == NULL) return result;st.push(root);while (!st.empty()) {TreeNode* node = st.top();st.pop();result.push_back(node->val);if (node->left) st.push(node->left); // 相对于前序遍历,这更改一下入栈顺序 (空节点不入栈)if (node->right) st.push(node->right); // 空节点不入栈}reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了return result;}
};
- 处理:将元素放进result数组中
- 访问:遍历节点
中序遍历:
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;TreeNode* cur = root;while (cur != NULL || !st.empty()) {if (cur != NULL) { // 指针来访问节点,访问到最底层st.push(cur); // 将访问的节点放进栈cur = cur->left; // 左} else {cur = st.top(); // 从栈里弹出的数据,就是要处理的数据(放进result数组里的数据)st.pop();result.push_back(cur->val); // 中cur = cur->right; // 右}}return result;}
};
102. 二叉树的层序遍历
给你二叉树的根节点
root
,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
代码示例:
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;vector<vector<int>> result;if(root != NULL) que.push(root);while(!que.empty()){int size = que.size();vector<int> vec;while(size--){TreeNode* node = que.front();que.pop();vec.push_back(node->val);if(node->left) que.push(node->left);if(node->right) que.push(node->right);}result.push_back(vec);}return result;}
};
107. 二叉树的层序遍历II
给你二叉树的根节点
root
,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
代码示例:
class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {queue<TreeNode*> que;vector<vector<int>> result;if(root != NULL) que.push(root);while(!que.empty()){int size = que.size();vector<int> vec;while(size--){TreeNode* node = que.front();que.pop();vec.push_back(node->val);if(node->left) que.push(node->left);if(node->right) que.push(node->right);} result.push_back(vec);}reverse(result.begin(),result.end());return result;}
};
注意:
以下写法是错的,因为
reverse
函数不返回任何值(返回类型是void
),它只是对输入范围内的元素进行原地修改。return reverse(result.begin(),result.end());
199. 二叉树的右视图
给定一个二叉树的 根节点
root
,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
代码示例:
class Solution {
public:vector<int> rightSideView(TreeNode* root) {queue<TreeNode*> que;vector<int> result;if(root != NULL) que.push(root);while(!que.empty()){int size = que.size();for(int i = 0;i<size;i++){TreeNode* node = que.front();que.pop();if(i == (size - 1)) result.push_back(node->val);if(node->left) que.push(node->left);if(node->right) que.push(node->right);}} return result;}
};
226. 翻转二叉树
给你一棵二叉树的根节点
root
,翻转这棵二叉树,并返回其根节点。
代码示例:
class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (root == NULL) return root;swap(root->left, root->right); // 中invertTree(root->left); // 左invertTree(root->right); // 右return root;}
};
101. 对称二叉树
给你一个二叉树的根节点
root
, 检查它是否轴对称。
代码示例:
class Solution {
public:bool compare(TreeNode* left, TreeNode* right) {// 首先排除空节点的情况if (left == NULL && right != NULL) return false;else if (left != NULL && right == NULL) return false;else if (left == NULL && right == NULL) return true;// 排除了空节点,再排除数值不相同的情况else if (left->val != right->val) return false;// 此时就是:左右节点都不为空,且数值相同的情况// 此时才做递归,做下一层的判断bool outside = compare(left->left, right->right); // 左子树:左、 右子树:右bool inside = compare(left->right, right->left); // 左子树:右、 右子树:左bool isSame = outside && inside; // 左子树:中、 右子树:中 (逻辑处理)return isSame;}bool isSymmetric(TreeNode* root) {if (root == NULL) return true;return compare(root->left, root->right);}
};
104. 二叉树的最大深度
给定一个二叉树
root
,返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
二叉树的 最大高度 是指最从远叶子节点到根节点的最长路径上的节点数。
代码示例:
class Solution {
public:int getdepth(TreeNode* node) {if (node == NULL) return 0;int leftdepth = getdepth(node->left); // 左int rightdepth = getdepth(node->right); // 右int depth = 1 + max(leftdepth, rightdepth); // 中return depth;}int maxDepth(TreeNode* root) {return getdepth(root);}
};
111. 二叉树的最小深度
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。
代码示例:
class Solution {
public:int getDepth(TreeNode* node) {if (node == NULL) return 0;int leftDepth = getDepth(node->left); // 左int rightDepth = getDepth(node->right); // 右// 中// 当一个左子树为空,右不为空,这时并不是最低点if (node->left == NULL && node->right != NULL) { return 1 + rightDepth;} // 当一个右子树为空,左不为空,这时并不是最低点if (node->left != NULL && node->right == NULL) { return 1 + leftDepth;}int result = 1 + min(leftDepth, rightDepth);return result;}int minDepth(TreeNode* root) {return getDepth(root);}
};
222. 完全二叉树的节点个数
给你一棵 完全二叉树 的根节点
root
,求出该树的节点个数。完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第
h
层,则该层包含1~ 2h
个节点。
代码示例(普通二叉树解法):
class Solution {
private:int getNodesNum(TreeNode* cur) {if (cur == NULL) return 0;int leftNum = getNodesNum(cur->left); // 左int rightNum = getNodesNum(cur->right); // 右int treeNum = leftNum + rightNum + 1; // 中return treeNum;}
public:int countNodes(TreeNode* root) {return getNodesNum(root);}
};
完全二叉树解法:
class Solution {
public:int countNodes(TreeNode* root) {if (root == nullptr) return 0;TreeNode* left = root->left;TreeNode* right = root->right;int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的,为了下面求指数方便while (left) { // 求左子树深度left = left->left;leftDepth++;}while (right) { // 求右子树深度right = right->right;rightDepth++;}if (leftDepth == rightDepth) {return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2,所以leftDepth初始为0}return countNodes(root->left) + countNodes(root->right) + 1;}
};
参考如下:
代码随想录
相关文章:

LeetCode---二叉树
144/94/145. 二叉树的前、中、后序的递归遍历 以中序遍历为例,其余类似: 给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。 代码示例: /*** Definition for a binary tree node.* struct TreeNode {* int val;* Tr…...
从0开发一个Chrome插件:核心功能开发——弹出页面
前言 这是《从0开发一个Chrome插件》系列的第十一篇文章,本系列教你如何从0去开发一个Chrome插件,每篇文章都会好好打磨,写清楚我在开发过程遇到的问题,还有开发经验和技巧。 专栏: 从0开发一个Chrome插件:什么是Chrome插件?从0开发一个Chrome插件:开发Chrome插件的必…...
AIGC笔记--Stable Diffusion源码剖析之UNetModel
1--前言 以论文《High-Resolution Image Synthesis with Latent Diffusion Models》 开源的项目为例,剖析Stable Diffusion经典组成部分,巩固学习加深印象。 2--UNetModel 一个可以debug的小demo:SD_UNet 以文生图为例&#…...

Linux文件系统与日志分析
目录 inode block 链接 文件修复 实验步骤 针对ext文件系统恢复删除文件 针对xfs文件系统恢复删除文件 日志 日志级别 rsyslogd服务 日志目录 messages日志文件(系统日志) 集中管理日志 - 实验 1.环境配置 1.1 1.2 1.3 1.4 1.5 2.远…...

【SkyWalking】使用PostgreSQL做存储K8s部署
拉取镜像 docker pull apache/skywalking-ui:10.0.1 docker tag apache/skywalking-ui:10.0.1 xxx/xxx/skywalking-ui:10.0.1 docker push xxx/xxx/skywalking-ui:10.0.1docker pull apache/skywalking-oap-server:10.0.1 docker tag apache/skywalking-oap-server:10.0.1 xxx…...

详解大模型微调数据集构建方法(持续更新)
大家好,我是herosunly。985院校硕士毕业,现担任算法t研究员一职,热衷于机器学习算法研究与应用。曾获得阿里云天池比赛第一名,CCF比赛第二名,科大讯飞比赛第三名。拥有多项发明专利。对机器学习和深度学习拥有自己独到的见解。曾经辅导过若干个非计算机专业的学生进入到算…...

自制植物大战僵尸:HTML5与JavaScript实现的简单游戏
引言 在本文中,我们将一起探索如何使用HTML5和JavaScript来创建一个简单的植物大战僵尸游戏。这不仅是一项有趣的编程挑战,也是学习游戏开发基础的绝佳机会。 什么是植物大战僵尸? 植物大战僵尸是一款流行的策略塔防游戏,玩家需…...

Istio_1.17.8安装
项目背景 按照istio官网的命令一路安装下来,安装好的istio版本为目前的最新版本,1.22.0。而我的k8s集群的版本并不支持istio_1.22的版本,导致ingress-gate网关安装不上,再仔细查看istio的发布文档,如果用istio_1.22版本…...

[数据集][目标检测]室内积水检测数据集VOC+YOLO格式761张1类别
数据集格式:Pascal VOC格式YOLO格式(不包含分割路径的txt文件,仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数):761 标注数量(xml文件个数):761 标注数量(txt文件个数):761 标注类别…...

17_Vue高级监听器生命周期Vue组件组件通信
文章目录 1. 数据监听器watch2. Vue生命周期3. Vue组件4. Vue组件通信Appendix 1. 数据监听器watch 首先watch需要单独引 import {watch} from vuewatch函数监听ref响应式数据 watch(监听的内容,监听行为)监听行为默认为(newValue,oldValue) let firstname ref…...

【ROS使用记录】—— ros使用过程中的rosbag录制播放和ros话题信息相关的指令与操作记录
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、rosbag的介绍二、rosbag的在线和离线录制三、rosbag的播放相关的指令四、其他rosbag和ros话题相关的指令总结 前言 rosbag是ROS(机器人操作系统…...
Laravel 富文本内容
Laravel 获取富文本的纯文本内容-CSDN博客 Laravel 富文本内容里面的图片添加前缀URL-CSDN博客 Laravel 富文本图片的style样式删除-CSDN博客. Laravel 获取富文本中的所有图片-CSDN博客 富文本字体font-famly删除 $data preg_replace(/(<[^>])style["\][^"…...
Spark Python环境搭建与优化:深入剖析四个方面、五个方面、六个方面及七个关键要点
Spark Python环境搭建与优化:深入剖析四个方面、五个方面、六个方面及七个关键要点 在大数据处理领域,Apache Spark凭借其出色的性能和灵活性备受瞩目。而要在Python中利用Spark的强大功能,首先需要搭建一个稳定且高效的Spark Python环境。本…...

【微信小程序开发】小程序中的上滑加载更多,下拉刷新是如何实现的?
✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,…...

从 Android 恢复已删除的备份录
本文介绍了几种在 Android 上恢复丢失和删除的短信的方法。这些方法都不能保证一定成功,但您可能能够恢复一些短信或其中存储的文件。 首先要尝试什么 首先,尝试保留数据。如果你刚刚删除了信息,请立即将手机置于飞行模式,方法是…...
如何使用Python中的random模块生成随机数
在Python中,random模块提供了多种用于生成随机数的函数。以下是一些基本示例: 生成随机整数: 使用random.randint(a, b)函数生成一个介于a和b之间的随机整数(包括a和b)。 python复制代码 import random random_int …...

AI大数据处理与分析实战--体育问卷分析
AI大数据处理与分析实战–体育问卷分析 前言:前一段时间接了一个需求,使用AI进行数据分析与处理,遂整理了一下大致过程和大致简要结果(更详细就不方便放了)。 文章目录 AI大数据处理与分析实战--体育问卷分析一、数据…...

C++第二十五弹---从零开始模拟STL中的list(下)
✨个人主页: 熬夜学编程的小林 💗系列专栏: 【C语言详解】 【数据结构详解】【C详解】 目录 1、函数补充 2、迭代器完善 3、const迭代器 总结 1、函数补充 拷贝构造 思路: 先构造一个头结点,然后将 lt 类中的元…...
STM32/keil把多个c文件编译为静态库lib
把常用的、不经常修改的代码库编译成lib以后,可以加快整个工程的编译速度。 一个常见的应用场景就是,把ST的标准库或HAL库等编译成lib,这样以后再编译整个工程时,就无需再次编译他们了,可以节省编译时间。当然&#x…...

L45---506.相对名次(java)--排序
1.题目描述 2.知识点 (1)String.join(" ", words) 是 Java 中的一个语法,用于将数组或集合中的元素连接成一个单独的字符串,连接时使用指定的分隔符。这里的 " " 是作为分隔符使用的一个空格字符串。 Strin…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...

7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...

简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...

Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...

初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...