当前位置: 首页 > news >正文

刷题 二叉树

二叉树的核心思想 - 递归 - 将问题分解为子问题

题型

  • 递归遍历
  • 迭代遍历
  • 层序遍历 bfs:队列
  • 各种递归题目:将问题分解为子问题
  • 二叉搜索树 - 中序遍历是递增序列 TreeNode* &prev 指针
  • 树形dp

面试经典 150 题 - 二叉树

104. 二叉树的最大深度

在这里插入图片描述

广度优先遍历

class Solution {
public:// 广度优先遍历int maxDepth(TreeNode* root) {if (root == nullptr) return 0;queue<TreeNode*> que;que.push(root);int result = 0;while (!que.empty()) {++result;int num = que.size();while (num--) {TreeNode* cur = que.front();que.pop();if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);}}return result;}
};

递归

最大深度 = 1 + max(左子树最大深度, 右子树最大深度)

class Solution {
public:// 递归:最大深度 = 1 + max(左子树最大深度, 右子树最大深度)int maxDepth(TreeNode* root) {if (root == nullptr) return 0;return 1 + max(maxDepth(root->left), maxDepth(root->right));}
};

100. 相同的树

在这里插入图片描述

递归

树相同 --> 根节点相同 + 左子树相同 + 右子树相同

class Solution {
public:// 递归// 树相同 --> 根节点相同 + 左子树相同 + 右子树相同bool isSameTree(TreeNode* p, TreeNode* q) {if (p == nullptr && q == nullptr) {return true;} else if (p == nullptr || q == nullptr) {return false;}if (p->val != q->val) {return false;}if (isSameTree(p->left, q->left) == false) {return false;}if (isSameTree(p->right, q->right) == false) {return false;}return true;}
};

226. 翻转二叉树

在这里插入图片描述

递归

class Solution {
public:// 翻转二叉树 --> // 根节点的左子树 = 将右子树进行反转// 根节点的右子树 = 将左子树进行反转TreeNode *invertTree(TreeNode *root) {if (root == nullptr) return nullptr;auto left = invertTree(root->left); // 翻转左子树auto right = invertTree(root->right); // 翻转右子树root->left = right; // 交换左右儿子root->right = left;return root;}
};

⭐️⭐️112. 路径总和

在这里插入图片描述

回溯

class Solution {
public:// 回溯bool backtracking(TreeNode* root, int path_sum, int targetSum) { if (root == nullptr) return false;if (root->right == nullptr && root->left == nullptr) {  // 到达叶子节点,终止回溯return (path_sum + root->val == targetSum);}return (backtracking(root->left, path_sum + root->val, targetSum) || \backtracking(root->right, path_sum + root->val, targetSum));}bool hasPathSum(TreeNode* root, int targetSum) {return backtracking(root, 0, targetSum);}
};

⭐️⭐️迭代

class Solution {
public:// 递归: 树 存在和为 targetSum// 也即左子树存在和为 targetSum - root->val 或者 右子树存在和为 targetSum - root->valbool hasPathSum(TreeNode* root, int targetSum) {if (root == nullptr) return false;if (root->left == nullptr && root->right == nullptr) {return (targetSum == root->val); } return (hasPathSum(root->left, targetSum - root->val) || \hasPathSum(root->right, targetSum - root->val));}
};

层序遍历

比较简单,不做讨论

面试经典 150 题 - 二叉树层次遍历

199. 二叉树的右视图

class Solution {
public:vector<int> rightSideView(TreeNode* root) {if (root == nullptr) return vector<int>{};queue<TreeNode*> que;que.push(root);vector<int> result;while (!que.empty()) {size_t n = que.size();for (size_t i = 0; i < n; ++i) {TreeNode* cur = que.front();que.pop();if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);if (i ==  n - 1) result.push_back(cur->val);}}return result;}
};

637. 二叉树的层平均值

class Solution {
public:vector<double> averageOfLevels(TreeNode* root) {if (root == nullptr) return vector<double>{};queue<TreeNode*> que;que.push(root);vector<double> result;while (!que.empty()) {size_t n = que.size();double sum = 0.0;for (size_t i = 0; i < n; ++i) {TreeNode* cur = que.front();que.pop();if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);sum += cur->val;}result.push_back(sum / n);}return result;}
};

[102. 二叉树的层序遍历

](https://leetcode.cn/problems/binary-tree-level-order-traversal/?envType=study-plan-v2&envId=top-interview-150)

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {if (root == nullptr) return vector<vector<int>>{};queue<TreeNode*> que;que.push(root);vector<vector<int>> result;while (!que.empty()) {size_t n = que.size();vector<int> layer(n, 0);for (size_t i = 0; i < n; ++i) {TreeNode* cur = que.front();que.pop();if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);layer[i] = cur->val;}result.push_back(layer);}return result;}
};

103. 二叉树的锯齿形层序遍历 - 写入的时候改一下索引即可

在这里插入图片描述

class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {if (root == nullptr) return vector<vector<int>>{};queue<TreeNode*> que;que.push(root);vector<vector<int>> result;bool to_right = false;while (!que.empty()) {to_right = !to_right;size_t n = que.size();vector<int> layer(n, 0);for (size_t i = 0; i < n; ++i) {TreeNode* cur = que.front();que.pop();if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);if (to_right) {layer[i] = cur->val;} else {layer[n - 1 - i] = cur->val;}}result.push_back(layer);}return result;}
};

面试经典 150 题 - 二叉搜索树 - ⭐️TreeNode*& prev⭐️ - 中序遍历有序

98. 验证二叉搜索树

class Solution {
public:bool traversal(TreeNode* root, TreeNode*& prev) {if (root == nullptr) return true;if (!traversal(root->left, prev)) return false;if (prev != nullptr && prev->val >= root->val) return false;prev = root;return traversal(root->right, prev);}bool isValidBST(TreeNode* root) {TreeNode* prev = nullptr;return traversal(root, prev);}
};

530. 二叉搜索树的最小绝对差

在这里插入图片描述

使用数组暂存

class Solution {
public:// 二叉搜索树的特征:左子树 < 根节点 < 右子树// 中序遍历即可获得最小差值void traversal(TreeNode* root, vector<int>& vals, int& min_diff) {if (root == nullptr) return;traversal(root->left, vals, min_diff);if (!vals.empty()) min_diff = min(min_diff, root->val - vals.back()); vals.push_back(root->val);traversal(root->right, vals, min_diff);}int getMinimumDifference(TreeNode* root) {vector<int> vals;int min_diff = INT_MAX;traversal(root, vals, min_diff);return min_diff;}
};

⭐️优化 - 使用一个 prev_val 即可

class Solution {
public:// 二叉搜索树的特征:左子树 < 根节点 < 右子树// 中序遍历即可获得最小差值// 如果不想使用数组暂存的话就需要存储一个 prev 指针void traversal(TreeNode* root, TreeNode*& prev, int& min_diff) {if (root == nullptr) return;traversal(root->left, prev, min_diff);if (prev != nullptr) min_diff = min(min_diff, root->val - prev->val); prev = root;traversal(root->right, prev, min_diff);}int getMinimumDifference(TreeNode* root) {int min_diff = INT_MAX;TreeNode* prev = nullptr;traversal(root, prev, min_diff);return min_diff;}
};

230. 二叉搜索树中第 K 小的元素 - 想象用数组存储元素 - 实际只使用索引即可 - 注意终止条件

class Solution {
public:void traversal(TreeNode* root, int& val, int& count, int k) {if (root == nullptr || count >= k) return;  // 递归终止条件traversal(root->left, val, count, k);++count;    // 如果用数组存储元素,想象这里是数组的第 count 个数字(从0开始)if (count == k) {val = root->val;return;}traversal(root->right, val, count, k);}int kthSmallest(TreeNode* root, int k) {int val, count = 0;traversal(root, val, count, k);return val;}
};

相关文章:

刷题 二叉树

二叉树的核心思想 - 递归 - 将问题分解为子问题 题型 递归遍历迭代遍历层序遍历 bfs&#xff1a;队列各种递归题目&#xff1a;将问题分解为子问题二叉搜索树 - 中序遍历是递增序列 TreeNode* &prev 指针树形dp 面试经典 150 题 - 二叉树 104. 二叉树的最大深度 广度优…...

操作系统 | 学习笔记 | 王道 | 4.1 文件系统基础

4.文件管理 4.1 文件系统基础 4.1.1 文件的基本概念 定义 文件是以计算机硬盘为载体的存储在计算机上的信息集合&#xff0c;在用户进行的输入、输出中&#xff0c;以文件位基本单位。 文件管理系统是实现的文件的访问、修改和保存&#xff0c;对文件维护管理的系统。 文件的…...

var let const 之间的区别

在JavaScript中&#xff0c;var、let 和 const 是用于声明变量的三种关键字。它们之间有几个重要的区别&#xff1a; 1. 作用域 var: 声明的变量具有函数作用域&#xff0c;即在整个函数内都可以访问。如果在代码块内&#xff08;如if或for&#xff09;使用var&#xff0c;该…...

【springboot】简易模块化开发项目整合Swagger2

接上一项目【springboot】简易模块化开发项目整合MyBatis-plus&#xff0c;进行拓展项目 1.新建模块 右键项目→New→Module&#xff0c;新建一个模块 父项目选择fast-demo&#xff0c;命名为fast-demo-config&#xff0c;用于存放所有配置项 添加后&#xff0c;项目结构如图…...

【Linux第五课-进程概念下】环境变量、程序地址空间

目录 环境变量main参数 --- 命令行参数环境变量环境变量特性 --- 命令行操作main函数的参数获取环境变量environ获取环境变量getenv()获取环境变量unset移除本地变量或环境变量set显示本地变量 代码获取和设置环境变量 本地变量 程序地址空间什么是进程地址空间为什么有地址空间…...

mysql学习教程,从入门到精通,SQL 临时表(37)

1、SQL 临时表 在SQL中&#xff0c;临时表&#xff08;Temporary Table&#xff09;是一种在会话或连接期间临时存储数据的表。它们对于存储中间结果、简化复杂查询以及提高性能非常有用。以下是一个创建和使用临时表的示例。 假设我们有一个名为 employees 的表&#xff0c;…...

算法闭关修炼百题计划(四)

仅供个人复习 1.两数相加2.寻找峰值6.岛屿的最大面积3.最大数4.会议室5.最长连续序列6.寻找两个正序数组的中位数 1.两数相加 给你两个 非空 的链表&#xff0c;表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的&#xff0c;并且每个节点只能存储 一位 数字。 请…...

头歌实践教学平台 大数据编程 实训答案(二)

第三阶段 Spark算子综合案例 Spark算子综合案例 - JAVA篇 第1关:WordCount - 词频统计 任务描述 本关任务:使用 Spark Core 知识编写一个词频统计程序。 相关知识 略 编程要求 请仔细阅读右侧代码,根据方法内的提示,在Begin - End区域内进行代码补充,具体任务如下: …...

路由交换实验指南

案例 01&#xff1a;部署使用 eNSP 平台实验需求&#xff1a; 安装华为 eNSP 网络模拟平台打开 eNSP 平台&#xff0c;新建拓扑并绘制网络能够成功启动交换机、计算机设备 实验步骤&#xff1a; 安装华为 eNSP 网络模拟平台启动安装程序 配置安装内容 防护墙允许 eNSP 程序的…...

了解网页 blob 链接

blob 链接 自从 HTML5 提供了 video 标签&#xff0c;在网页中播放视频变得非常简单&#xff0c;只要在代码中插入一个 video 标签&#xff0c;再将 video 标签的 src 属性设置为视频的链接就可以了。由于 src 指向的是视频文件真实的地址&#xff0c;所以当我们通过浏览器的调…...

OpenGL笔记之事件驱动设计将相机控制类和应用程序类分离

OpenGL笔记之事件驱动设计将相机控制类和应用程序类分离 —— 2024-10-02 下午 bilibili赵新政老师的教程看后笔记 code review! 文章目录 OpenGL笔记之事件驱动设计将相机控制类和应用程序类分离1.代码图片2.分析3.UML4.代码 1.代码图片 运行 Mouse button 1 pressed at (1…...

低代码时代的企业信息化:规范与标准化的重要性

在当今数字化转型的浪潮中&#xff0c;企业的信息化建设正逐步向低代码平台倾斜。低代码不仅仅是简化开发过程&#xff0c;更是对企业内部流程、规范和标准化的深刻理解与应用。本文将探讨低代码在企业信息化中的重要性&#xff0c;特别是在运维和开发流程中的标准化&#xff0…...

理解无监督学习、无监督图像分割

系列文章目录 文章目录 系列文章目录一、无监督学习如何学习 能不能举一个非常具体的例子&#xff0c;带着运算过程的例子总结 二、在图像分割中呢&#xff0c;具体怎样实现无监督示例&#xff1a;使用自编码器和k-means进行无监督图像分割1. **数据准备**2. **构建自编码器**3…...

C语言— exec系列函数

exec系列函数 在C语言编程中&#xff0c;exec 系列函数用于在当前进程中执行一个新程序&#xff0c;从而替换当前进程的映像。这些函数不会返回&#xff0c;除非发生错误。exec 系列函数有多个变体&#xff0c;其中最常用的包括 execl, execle, execlp, execv, execve, execvp…...

命名管道Linux

管道是 毫不相关的进程进程间通信::命名管道 管道 首先自己要用用户层缓冲区&#xff0c;还得把用户层缓冲区拷贝到管道里&#xff0c;&#xff08;从键盘里输入数据到用户层缓冲区里面&#xff09;&#xff0c;然后用户层缓冲区通过系统调用&#xff08;write&#xff09;写…...

【ios】---swift开发从入门到放弃

swift开发从入门到放弃 环境swift入门变量与常量类型安全和类型推断print函数字符串整数双精度布尔运算符数组集合set字典区间元祖可选类型循环语句条件语句switch语句函数枚举类型闭包数组方法结构体 环境 1.在App Store下载Xcode 2.新建项目&#xff08;可以先使用这个&…...

【AUTOSAR 基础软件】PduR模块详解(通信路由)

文章包含了AUTOSAR基础软件&#xff08;BSW&#xff09;中PduR模块相关的内容详解。本文从AUTOSAR规范解析&#xff0c;ISOLAR-AB配置以及模块相关代码分析三个维度来帮读者清晰的认识和了解PduR这一基础软件模块。文中涉及的ISOLAR-AB配置以及模块相关代码都是依托于ETAS提供的…...

[控制理论]—差分变换法与双线性变换法的基本原理和代码实现

差分变换法与双线性变换法的基本原理和代码实现 1.差分变换法 差分变换法就是把微分方程中的导数用有限差分来近似等效&#xff0c;得到一个与原微分方程逼近的差分方程。 差分变换法包括后向差分与前向差分。 1.1 后向差分法 差分变换如下&#xff1a; d e ( t ) d t e…...

【JavaEE】——多线程常用类

阿华代码&#xff0c;不是逆风&#xff0c;就是我疯 你们的点赞收藏是我前进最大的动力&#xff01;&#xff01; 希望本文内容能够帮助到你&#xff01;&#xff01; 目录 引入&#xff1a; 一&#xff1a;Callable和FutureTask类 1&#xff1a;对比Runnable 2&#xff1a…...

Cilium-实战系列-(二)Cilium-Multi Networking-多网络

一、Cilium必要开启的功能 1、enable-multi-network 2、ipam模式选择:multi-pool 二、涉及的CRD资源 1、 ciliumpodippools.cilium.io *通过Cilium管理节点上的pod cidr.网络分为主网络和第二网络。 *主网络的 ciliumpodippools.cilium.io default根据配置文件默认生成的。 …...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)

题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...

水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关

在水泥厂的生产流程中&#xff0c;工业自动化网关起着至关重要的作用&#xff0c;尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关&#xff0c;为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多&#xff0c;其中不少设备采用Devicenet协议。Devicen…...

数据库正常,但后端收不到数据原因及解决

从代码和日志来看&#xff0c;后端SQL查询确实返回了数据&#xff0c;但最终user对象却为null。这表明查询结果没有正确映射到User对象上。 在前后端分离&#xff0c;并且ai辅助开发的时候&#xff0c;很容易出现前后端变量名不一致情况&#xff0c;还不报错&#xff0c;只是单…...