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

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...