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

二叉树的深搜

前言: 本章节更深入学习递归

计算布尔二叉树的值

 

思路: 
1.函数头设计:dfs(root)

2.函数体:需要一个接收left 和 right 的值  并且根据root的值进行比较

3.递归出口:很明显 当为叶子节点的时候 向上返回你叶子节点的值 并且与当前root的值进行比较

    public boolean evaluateTree(TreeNode root) {if(root.left == null && root.right == null) {return root.val > 0;}boolean left = evaluateTree(root.left);boolean right = evaluateTree(root.right);return root.val == 2 ? left || right : left && right;}

求根节点到叶节点数字之和

 

从根节点开始,遍历每个节点,如果遇到叶子节点,则将叶子节点对应的数字加到数字之和。如果当前节点不是叶子节点,则计算其子节点对应的数字,然后对子节点递归遍历。

    int ret = 0;public int sumNumbers(TreeNode root) {return dfs(root, 0);}public int dfs(TreeNode root, int preSum) {preSum = preSum * 10 + root.val;if (root.left == null && root.right == null) {return ret += preSum;}if (root.left != null) {dfs(root.left, preSum);}if (root.right != null) {dfs(root.right, preSum);}return ret;}

 二叉树剪枝

 

思路: 叶子节点为0 直接让它指向空  后序遍历思想

1.遍历完左子树 再遍历右子树

2. 如果遇到叶子节点 则判断当前节点是否为0 

3.如果为0 则直接返回null  否则不需要剪枝 直接返回原来值

    public TreeNode pruneTree(TreeNode root) {if (root == null) {return null;}root.left = pruneTree(root.left);root.right = pruneTree(root.right);if (root.left == null && root.right == null && root.val == 0) {return null;} else {return root;}}

验证二叉搜索树

思路:二叉搜索树 中序遍历是一个有序数组 利用这一特性
先定义一个最小数字prev

当遍历完左子树回退时候

比较是否prev跟当前回退的数字大小 

如果比prev大 则让prev=当前节点的值 

否则 就不是二叉搜索树

    long prev = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if (root == null) {return true;}if (!isValidBST(root.left) || root.val <= prev) {return false;}prev = root.val;return isValidBST(root.right);}

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

 思路: 要求二叉搜索树第k大的数字

定义俩个全局变量 ret记录最终结果 count记录当前k

依次遍历到左子树 当为空的时候 就该回退了

并且 count-1 当count为0的时候 就是目标值了

 int ret;int count ;public int kthSmallest(TreeNode root, int k) {count = k;dfs(root);return ret;}public void dfs(TreeNode root) {if(root == null) {return ;}dfs(root.left);count--;if(count == 0) {ret = root.val;return ;}dfs(root.right);}

 

相关文章:

二叉树的深搜

前言&#xff1a; 本章节更深入学习递归 计算布尔二叉树的值 思路&#xff1a; 1.函数头设计&#xff1a;dfs&#xff08;root&#xff09; 2.函数体&#xff1a;需要一个接收left 和 right 的值 并且根据root的值进行比较 3.递归出口&#xff1a;很明显 当为叶子节点的时候…...

JUC笔记之ReentrantLock

ReentrantLock 相对于synchronized它具备如下特点 可中断 可以设置超时时间 可以设置为公平锁 支持多个条件变量(多个wait set,不同于synchronized的wait set,ReentrantLock的wait set在同一条件下notify才能唤醒WATING状态的线程) 与synchronized一样,都支持可重入 …...

【含文档】基于ssm+jsp的图书管理系统(含源码+数据库+lw)

1.开发环境 开发系统:Windows10/11 架构模式:MVC/前后端分离 JDK版本: Java JDK1.8 开发工具:IDEA 数据库版本: mysql5.7或8.0 数据库可视化工具: navicat 服务器: apache tomcat 主要技术: Java,Spring,SpringMvc,mybatis,mysql,vue 2.视频演示地址 3.功能 系统定义了两个…...

pytorch知识蒸馏测试

import torch from torch import nn,optim import torch.utils import torch.utils.data import torch.utils.data.dataloader from torchvision import transforms,datasets...

mutable用法

mutable 关键字用于允许类的某个成员变量在 const 成员函数中被修改。通常&#xff0c;const 成员函数不能改变对象的任何成员变量&#xff0c;但将成员变量声明为 mutable 可以例外 class Hero { public:Hero():m_Hp(0), m_getHpCounter(0){}int getHp() const {m_getHpCounte…...

SQL语言基础

SQL(Struct Query Language)是结构化查询语言的简称&#xff0c;是一种在关系型数据库中定义和操纵数据的标准语言。 不要使用面向对象的思想学习SQL&#xff0c;因为它不是面向对象的语言目标 SQL语言简介(了解)从数据库数据检索数据(重点)子查询(重点)Oracle常用函数(掌握) …...

在USB电源测试中如何降低测试成本?-纳米软件

USB 电源模块在现代电子设备中广泛应用&#xff0c;其性能的稳定性和可靠性至关重要。然而&#xff0c;测试 USB 电源模块的成本可能会很高&#xff0c;这对于企业和研发机构来说是一个重要的问题。因此&#xff0c;寻找降低 USB 电源模块测试成本的方法具有重要的现实意义。 降…...

springboot - 定时任务

定时任务是企业级应用中的常见操作 定时任务是企业级开发中必不可少的组成部分&#xff0c;诸如长周期业务数据的计算&#xff0c;例如年度报表&#xff0c;诸如系统脏数据的处理&#xff0c;再比如系统性能监控报告&#xff0c;还有抢购类活动的商品上架&#xff0c;这些都离不…...

一篇文章理解CSS垂直布局方法

方法1&#xff1a;align-content: center 在 2024 年的 CSS 原生属性中允许使用 1 个 CSS 属性 align-content: center进行垂直居中。 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta name"viewpo…...

SpringBoot day 1105

ok了家人们&#xff0c;今天继续学习spring boot&#xff0c;let‘s go 六.SpringBoot实现SSM整合 6.1 创建工程&#xff0c;导入静态资源 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Title</…...

MySQL 完整教程:从入门到精通

MySQL 完整教程&#xff1a;从入门到精通 MySQL 是一个广泛使用的关系型数据库管理系统&#xff0c;它使用结构化查询语言 (SQL) 来管理和操作数据。本文将详细介绍 MySQL 的基本概念、安装与配置、常用 SQL 语法、数据表的创建与管理、索引、视图、存储过程、触发器等高级特性…...

【贝叶斯公式】贝叶斯公式、贝叶斯定理、贝叶斯因子,似然比

一、是什么&#xff1f; 贝叶斯公式的本质在于它提供了一种在已有知识的基础上更新和调整我们对事件的信念的方式。具体来说&#xff0c;贝叶斯公式描述了后验概率&#xff08;即在观察到某些证据后更新的概率&#xff09;与先验概率&#xff08;即在没有观察证据之前的概率&a…...

[libos源码学习 1] Liboc协程生产者消费者举例

文章目录 1. CoRoutineEnv_t结构体用于管理协程环境 3 Liboc协程生产者消费者例子4 Liboc协程生产者消费者&#xff0c; 为什么队列不需要上锁&#xff1f;5. 两个协程访问资源不需要加队列吗5. 参考 1. CoRoutineEnv_t结构体用于管理协程环境 struct stCoRoutineEnv_t { stCo…...

Python OpenCV 图像改变

更改图像数据 通过 改像素点 或者 切片的区域 import cv2 import numpy as np img cv2.imread("image.jpg") print(img[3,5]) # 显示某位置(行3列5)的像素值( 如 [53 34 29] 它是有三通道 B G R 组成) img[3,5] (0,0,255) # 更改该位置的像素…...

k8s按需创建 PV和创建与使用 PVC

在 Kubernetes 中&#xff0c;PersistentVolume&#xff08;PV&#xff09;和 PersistentVolumeClaim&#xff08;PVC&#xff09;用于管理存储资源。PV 是集群中的存储资源&#xff0c;而 PVC 是 Pod 请求 PV 的方式。按需创建 PV 通常使用 StorageClass 实现动态存储分配&…...

揭秘云计算 | 2、业务需求推动IT发展

揭秘云计算 | 1、云从哪里来&#xff1f;-CSDN博客https://blog.csdn.net/Ultipa/article/details/143430941?spm1001.2014.3001.5502 书接上文&#xff1a; 过去几十年间IT行业从大型主机过渡到客户端/服务器&#xff0c;再过渡到现如今的万物互联&#xff0c;IT可把控的资…...

【系统面试篇】进程与线程类(2)(笔记)——进程调度、中断、异常、用户态、核心态

目录 一、相关面试题 1. 进程的调度算法有哪些&#xff1f; 调度原则 &#xff08;1&#xff09;先来先服务调度算法 &#xff08;2&#xff09;最短作业优先调度算法 &#xff08;3&#xff09;高响应比优先调度算法 &#xff08;4&#xff09;时间片轮转调度算法 &am…...

基于MySQL的企业专利数据高效查询与统计实现

背景 在进行产业链/产业评估工作时&#xff0c;我们需要对企业的专利进行评估&#xff0c;其中一个重要指标是统计企业每一年的专利数量。本文基于MySQL数据库&#xff0c;通过公司名称查询该公司每年的专利数&#xff0c;实现了高效的专利数据统计。 流程 项目流程概述如下&…...

热成像手机VS传统热成像仪:AORO A23为何更胜一筹?

热成像技术作为一种非接触式测温方法&#xff0c;广泛应用于石油化工巡检、电力巡检、应急救援、医疗、安防等“危、急、特”场景。提及热成像设备&#xff0c;人们往往会首先想到价格高昂、操作复杂且便携性有限的热成像仪。但是&#xff0c;随着技术的不断进步&#xff0c;市…...

Spring IoC——依赖注入

1. 依赖注入的介绍 DI&#xff0c;也就是依赖注入&#xff0c;在容器中建立的 bean &#xff08;对象&#xff09;与 bean 之间是有依赖关系的&#xff0c;如果直接把对象存在 IoC 容器中&#xff0c;那么就都是一个独立的对象&#xff0c;通过建立他们的依赖关系&#xff0c;…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...