当前位置: 首页 > 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;…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...