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

二叉树的深搜(不定期更新。。。。。)

二叉树的深搜

在这里插入图片描述

验证二叉搜索树

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下:

  • 节点的左

    子树

    只包含

    小于

    当前节点的数。

  • 节点的右子树只包含 大于 当前节点的数。

  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

在这里插入图片描述

输入:root = [2,1,3]
输出:true

示例 2:

在这里插入图片描述

输入:root = [5,1,4,null,null,3,6]
输出:false
解释:根节点的值是 5 ,但是右子节点的值是 4 。

在这里插入图片描述

提示:

  • 树中节点数目范围在[1, 104]
  • -231 <= Node.val <= 231 - 1

解法(利⽤中序遍历):

后序遍历按照左⼦树、根节点、右⼦树的顺序遍历⼆叉树的所有节点,通常⽤于⼆叉搜索树相关题 ⽬。

算法思路:

如果⼀棵树是⼆叉搜索树,那么它的中序遍历的结果⼀定是⼀个严格递增的序列。 因此,我们可以初始化⼀个⽆穷⼩的全区变量,⽤来记录中序遍历过程中的前驱结点。那么就可以在 中序遍历的过程中,先判断是否和前驱结点构成递增序列,然后修改前驱结点为当前结点,传⼊下⼀ 层的递归中。

算法流程:

  1. 初始化⼀个全局的变量prev,⽤来记录中序遍历过程中的前驱结点的val;

  2. 中序遍历的递归函数中:

a. 设置递归出⼝:root==nullptr的时候,返回true;

b. 先递归判断左⼦树是否是⼆叉搜索树,⽤retleft标记;

c. 然后判断当前结点是否满⾜⼆叉搜索树的性质,⽤retcur标记:

▪ 如果当前结点的val⼤于prev,说明满⾜条件,retcur改为true;

▪ 如果当前结点的val⼩于等于prev,说明不满⾜条件,retcur改为false;

d. 最后递归判断右⼦树是否是⼆叉搜索树,⽤retright标记;

  1. 只有当retleft、retcur和retright都是true的时候,才返回true。

代码如下:

/*** 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 
{long prev = LONG_MIN;public:bool isValidBST(TreeNode* root) 
{if(root == nullptr) return true;bool left = isValidBST(root->left);// 剪枝if(left == false) return false;bool cur = false;if(root->val > prev)cur = true;// 剪枝if(cur == false) return false;prev = root->val;bool right = isValidBST(root->right);return left && right && cur;}};

二叉搜索树中第K小的元素

给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 小的元素(从 1 开始计数)。

示例 1:

在这里插入图片描述

输入:root = [3,1,4,null,2], k = 1
输出:1

示例 2:

在这里插入图片描述

输入:root = [5,3,6,2,4,null,null,1], k = 3
输出:3

提示:

  • 树中的节点数为 n
  • 1 <= k <= n <= 104
  • 0 <= Node.val <= 104

解法⼆(中序遍历+计数器剪枝):

算法思路:

上述解法不仅使⽤⼤量额外空间存储数据,并且会将所有的结点都遍历⼀遍。

但是,我们可以根据中序遍历的过程,只需扫描前k个结点即可。

因此,我们可以创建⼀个全局的计数器count,将其初始化为k,每遍历⼀个节点就将count–。直到 某次递归的时候,count的值等于1,说明此时的结点就是我们要找的结果。

算法流程:

  1. 定义⼀个全局的变量count,在主函数中初始化为k的值(不⽤全局也可以,当成参数传⼊递归过 程中);

递归函数的设计:int dfs(TreeNode * root):

• 返回值为第k个结点;

递归函数流程(中序遍历):

  1. 递归出⼝:空节点直接返回-1,说明没有找到;

  2. 去左⼦树上查找结果,记为retleft:

    a. 如果retleft==-1,说明没找到,继续执⾏下⾯逻辑;

    b. 如果retleft!=-1,说明找到了,直接返回结果,⽆需执⾏下⾯代码(剪枝);

    1. 如果左⼦树没找到,判断当前结点是否符合:

      a. 如果符合,直接返回结果

      1. 如果当前结点不符合,去右⼦树上寻找结果。

在这里插入图片描述

代码如下:

/*** 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 count=0;int ret=0;int kthSmallest(TreeNode* root, int k) {count=k;dfs(root);return ret;}void dfs(TreeNode*root){if(root==nullptr||count==0) return;dfs(root->left);count--;if(count==0)  ret=root->val;dfs(root->right);}
};

二叉树的所有路径

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

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

示例 1:

在这里插入图片描述

输入:root = [1,2,3,null,5]
输出:["1->2->5","1->3"]

示例 2:

输入:root = [1]
输出:["1"]

提示:

  • 树中节点的数目在范围 [1, 100]
  • -100 <= Node.val <= 100

在这里插入图片描述

解法(回溯):

算法思路:

使⽤深度优先遍历(DFS)求解。

路径以字符串形式存储,从根节点开始遍历,每次遍历时将当前节点的值加⼊到路径中,如果该节点 为叶⼦节点,将路径存储到结果中。否则,将"->"加⼊到路径中并递归遍历该节点的左右⼦树。 定义⼀个结果数组,进⾏递归。

递归具体实现⽅法如下:

  1. 如果当前节点不为空,就将当前节点的值加⼊路径path中,否则直接返回;

  2. 判断当前节点是否为叶⼦节点,如果是,则将当前路径加⼊到所有路径的存储数组paths中;

  3. 否则,将当前节点值加上"->"作为路径的分隔符,继续递归遍历当前节点的左右⼦节点。

  4. 返回结果数组。

    • 特别地,我们可以只使⽤⼀个字符串存储每个状态的字符串,在递归回溯的过程中,需要将路径中 的当前节点移除,以回到上⼀个节点。

    具体实现⽅法如下:

    1. 定义⼀个结果数组和⼀个路径数组。

    2. 从根节点开始递归,递归函数的参数为当前节点、结果数组和路径数组。

      a. 如果当前节点为空,返回。

      b. 将当前节点的值加⼊到路径数组中。

      c. 如果当前节点为叶⼦节点,将路径数组中的所有元素拼接成字符串,并将该字符串存储到结果 数组中。

      d. 递归遍历当前节点的左⼦树。

      e. 递归遍历当前节点的右⼦树。

      f. 回溯,将路径数组中的最后⼀个元素移除,以返回到上⼀个节点。

      1. 返回结果数组。

代码如下:

/*** 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> ret;vector<string> binaryTreePaths(TreeNode* root) {string path;if(root==nullptr) return ret;dfs(root,path);return ret;}void dfs(TreeNode*root,string path){path+=to_string(root->val);if(root->left==nullptr&&root->right==nullptr){ret.push_back(path);return ;}path+="->";if(root->left)  dfs(root->left,path);if(root->right)  dfs(root->right,path);}
};

相关文章:

二叉树的深搜(不定期更新。。。。。)

二叉树的深搜 验证二叉搜索树 给你一个二叉树的根节点 root &#xff0c;判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下&#xff1a; 节点的左 子树 只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉…...

WebLLM Chat:无服务器、私密的AI聊天体验

简介 什么是 Web-LLM ? Web-LLM 是一个高性能的浏览器内语言模型推理引擎&#xff0c;允许用户在没有服务器支持的情况下直接在网页浏览器中进行语言模型推理。它利用 WebGPU 进行硬件加速&#xff0c;从而实现强大的 LLM 操作。Web-LLM 完全兼容 OpenAI API&#xff0c;支持…...

C#中的模拟服务器与客户端建立连接

创建一个控制台项目&#xff0c;命名为Server&#xff0c;模拟服务器端。在同一个解决方案下&#xff0c;添加新项目&#xff0c;命名为Client&#xff0c;模拟客户端。在服务器端与客户端之间建立TCP连接&#xff0c;并在客户端发送消息&#xff0c;在服务器端输出。 Server项…...

【深度学习】利用Java DL4J 构建和训练医疗影像分析模型

🧑 博主简介:CSDN博客专家,历代文学网(PC端可以访问:https://literature.sinhy.com/#/literature?__c=1000,移动端可微信小程序搜索“历代文学”)总架构师,15年工作经验,精通Java编程,高并发设计,Springboot和微服务,熟悉Linux,ESXI虚拟化以及云原生Docker和K8s…...

application.yml 和 bootstrap.yml

在 Spring Boot 中&#xff0c;application.yml 和 bootstrap.yml 都是用来配置应用程序的属性文件&#xff0c;通常用于环境配置、服务配置等。但是&#xff0c;它们有一些不同的用途和加载顺序。以下是它们之间的主要区别&#xff1a; 1. application.yml&#xff1a; 主要…...

使用uniapp开发小程序场景:在百度地图上调用接口返回的设备相关信息并展示

首先在百度地图开发者平台注册微信小程序开发密钥下载百度地图SDK-bmap-wx.min.js,下载地址在项目入口index.html页面进行引入页面中进行调用&#xff0c;代码示例如下<map id"map" longitude"108.95" latitude"34.34" scale"3" :m…...

ubuntu22.04 使用可以用的镜像源获取你要的镜像

默认的是不行的 不管pull啥镜像 仍然会出现这个错误 Error response form daemon:Get "https://registry-1.docker.io/v2": net/http: request canceled while waiting for connection (Client.Timeout exceeded while await) 操作方法是 如果在目录没有/etc/docker…...

Flume——sink连接hdfs的参数配置(属性参数+时间参数)

这可不是目录 配置文件官网说明属性参数时间参数 配置文件官网说明 可以参考官网的说明 属性参数 属性名称默认值说明channel-type-组件类型名称&#xff0c;必须是hdfshdfs.path-HDFS路径&#xff0c;例如&#xff1a;hdfs://mycluster/flume/mydatahdfs.filePrefixFlumeDa…...

python+docker实现分布式存储的demo

test.py代码 #test.py from flask import Flask, request, jsonify import requests import sys import threadingapp Flask(__name__)# 存储数据 data_store {}# 节点列表&#xff0c;通过环境变量传入 nodes [] current_node Noneapp.route(/set, methods[POST]) def …...

go-blueprint create exit status 1

1. 异常信息 2024/12/06 10:59:19 Could not initialize go.mod in new project exit status 1 2024/12/06 10:59:19 Problem creating files for project. exit status 1 Error: exit status 12. 排查思路 手动进行go mod init查看手动的报错解决报错 3. 解决问题 发现是GO11…...

如何更改Git用户名 - 本地与全局设置指南

在开发过程中&#xff0c;当使用Git作为版本控制系统时&#xff0c;可能会遇到需要更改用户名的情况&#xff0c;适时更新Git配置是保持项目管理效率的重要环节。更改Git用户名可以帮助确保您的提交反映了当前的用户身份&#xff0c;这对于项目的协作和历史记录跟踪至关重要。 …...

Node.js JWT认证教程

Node.js JWT认证教程 1. 项目介绍 JSON Web Token (JWT) 是一种安全的跨域身份验证解决方案&#xff0c;在现代Web应用中广泛使用。本教程将详细讲解如何在Node.js中实现JWT认证。 2. 项目准备 2.1 初始化项目 # 创建项目目录 mkdir nodejs-jwt-auth cd nodejs-jwt-auth# …...

【青牛科技】应用于音频信号处理系统的D258 是由两个独立的高增益运算放大器组成

概述&#xff1a; D258是由两个独立的高增益运算放大器组成。可以是单电源工作&#xff0c;也可以是双电源工作,电源的电流消耗与电源电压大小无关。应用范围包括变频放大器、DC增益部件和所有常规运算放大电路。 主要特点&#xff1a; ● 可单电源或双电源 工作 ● 在一个封…...

HTML Input 文件上传功能全解析:从基础到优化

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…...

小程序 —— Day1

组件 — view和scroll-view view 类似于HTML中的div&#xff0c;是一个块级元素 案例&#xff1a;通过view组件实现页面的基础布局 scroll-view 可滚动的视图区域&#xff0c;用来实现滚动列表效果 案例&#xff1a;实现纵向滚动效果 scroll-x属性&#xff1a;允许横向滚动…...

4.5 TCP 报文段的首部格式

欢迎大家订阅【计算机网络】学习专栏&#xff0c;开启你的计算机网络学习之旅&#xff01; 文章目录 前言1 TCP 报文段的基本结构2 固定部分2.1 源端口与目的端口2.2 序号2.3 确认号2.4 数据偏移2.5 保留字段2.6 控制位2.7 窗口2.8 检验和2.9 紧急指针 3 可变部分3.1 选项3.2 填…...

SQL 获取今天的当月开始结束范围:

使用 GETDATE() 结合 DATEADD() 和 DATEDIFF() 函数来获取当前月的开始和结束时间范围。以下是实现当前月时间范围查询的 SQL&#xff1a; FDATE > DATEADD(MONTH, DATEDIFF(MONTH, 0, GETDATE()), 0) FDATE < DATEADD(MONTH, DATEDIFF(MONTH, 0, GETDATE()) 1, 0) …...

Qt复习学习

https://www.bilibili.com/video/BV1Jp4y167R9/?spm_id_from333.999.0.0&vd_sourceb3723521e243814388688d813c9d475f https://subingwen.cn/qt/qt-primer/#1-4-Qt%E6%A1%88%E4%BE%8B https://subingwen.cn/qt/ https://download.qt.io/archive/qt/1.1Qt的特点 1.2QT中的…...

Leetcode经典题5--轮转数组

题目描述 给定一个整数数组 nums&#xff0c;将数组中的元素向右轮转 k 个位置&#xff0c;其中 k 是非负数。 输入输出示例 &#xff1a; 输入: nums [1,2,3,4,5,6,7], k 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右…...

C++的一些经典算法

以下是C的一些经典算法&#xff1a; 一、排序算法 冒泡排序&#xff08;Bubble Sort&#xff09; 原理&#xff1a; 它重复地走访过要排序的数列&#xff0c;一次比较两个元素&#xff0c;如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

go 里面的指针

指针 在 Go 中&#xff0c;指针&#xff08;pointer&#xff09;是一个变量的内存地址&#xff0c;就像 C 语言那样&#xff1a; a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10&#xff0c;通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...

实战设计模式之模板方法模式

概述 模板方法模式定义了一个操作中的算法骨架&#xff0c;并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下&#xff0c;重新定义算法中的某些步骤。简单来说&#xff0c;就是在一个方法中定义了要执行的步骤顺序或算法框架&#xff0c;但允许子类…...