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

【刷题笔记】--两数之和Ⅳ,从二叉树中找出两数之和

2886aff88fe049ed9c43555c75e24a8a.png


 法一:深度搜索+中序遍历+双指针

思路:通过中序遍历二叉树得到一个递增的数列,再在这个递增的二叉树中找到这两数。

主要学到双指针这个方法。

对于一般数列,我们要找到两数满足其之和等于目标数,我们一般会进行暴力,即两重循环:

for(i=0;i<length;i++){for(j=i+1;j<length;j++){}
}

 对于暴力,我们要把下图的空白格全都依次检验,贼费时间。

f9efaea1d1ae4cafb6b2a008f73046f9.png


 而如果设置双指针,对应 i 和 j ,分别指向数组的头和尾。

如果a[0]+a[7]<target,说明a[0]+a[1],a[0]+a[2],a[0]+a[3],a[0]+a[4].....全都不满足,我们就可以直接把a[0]+的所有数给全部排除。 即把i=0时的那一排全排除了。

如果a[0]+a[7]>target,说明a[1]+a[7],a[2]+a[7],a[3]+a[7]......全不满足,我们就可以把j=7的那一列全排除了。

总结就是 i 是指向数组头的指针,如果i 右移,则删排,j 是指向数组尾的指针,如果j 左移,则删列。

这是缩减搜索空间的思想。

题解参考一张图告诉你 O(n) 的双指针解法的本质原理(C++/Java) - 两数之和 II - 输入有序数组 - 力扣(LeetCode)


代码:

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
void inorderTraversal(const struct TreeNode* node, int* vec, int* pos) {if (node == NULL) {return;}inorderTraversal(node->left, vec, pos);vec[(*pos)++] = node->val;inorderTraversal(node->right, vec, pos);
}bool findTarget(struct TreeNode* root, int k) {int * vec = (int *)malloc(sizeof(int) * 10000);int pos = 0;inorderTraversal(root, vec, &pos);int left = 0, right = pos - 1;while (left < right) {if (vec[left] + vec[right] == k) {return true;}if (vec[left] + vec[right] < k) {left++;} else {right--;}}free(vec);return false;
}

相关文章:

【刷题笔记】--两数之和Ⅳ,从二叉树中找出两数之和

法一&#xff1a;深度搜索中序遍历双指针 思路&#xff1a;通过中序遍历二叉树得到一个递增的数列&#xff0c;再在这个递增的二叉树中找到这两数。 主要学到双指针这个方法。 对于一般数列&#xff0c;我们要找到两数满足其之和等于目标数&#xff0c;我们一般会进行暴力&a…...

浏览器渲染原理JavaScript V8引擎

浏览器渲染原理 前言 在我们面试过程中&#xff0c;面试官经常会问到这么一个问题&#xff0c;那就是从在浏览器地址栏中输入URL到页面显示&#xff0c;浏览器到底发生了什么&#xff1f; 浏览器内有哪些进程&#xff0c;这些进程都有些什么作用&#xff1b;浏览器地址输入U…...

在TheSandbox 的「BOYS PLANET」元宇宙中与你的男孩们见面吧!

世界各的男孩们成为 K-Pop 男团的旅程。 Mnet 的全球项目 BOYS PLANET 终于在 2 月 2 日首次亮相&#xff01; The Sandbox 与 CJ ENM 合作&#xff0c;于 2 月 6 日晚上 10 点开始举办两个基于 BOYS PLANET 生存节目的虚拟体验&#xff1a;BOYS PLANET&#xff1a;BOYS LAND 和…...

数据结构与算法:java对象的比较

1.基本类型的比较 在Java中&#xff0c;基本类型的对象可以直接比较大小。 public class TestCompare {public static void main(String[] args) {int a 10;int b 20;System.out.println(a > b);System.out.println(a < b);System.out.println(a b);char c1 A;char…...

python(16)--类

一、类的基本操作1.定义一个类格式&#xff1a;class Classname( )&#xff1a;内容&#x1f48e;鄙人目前还是一名学生&#xff0c;最熟悉的也就是学校了&#xff0c;所以就以学校为例子来建立一个类吧class School():headline"帝国理工大学"def schoolmotto(self):…...

CNI 网络流量分析(七)Calico 介绍与原理(二)

文章目录CNI 网络流量分析&#xff08;七&#xff09;Calico 介绍与原理&#xff08;二&#xff09;CNIIPAM指定 IP指定非 IPAM IPCNI 网络流量分析&#xff08;七&#xff09;Calico 介绍与原理&#xff08;二&#xff09; CNI 支持多种 datapath&#xff0c;默认是 linuxDa…...

API安全的最大威胁:三体攻击

最近《三体》火的一塌糊涂,动画片、电视剧和书都受到了大家的喜爱。在API安全上,最近也发现了三体攻击。 当然了,肯定是不来自于三体人的攻击,这里的三体攻击指的是(trinity,也称三位一体攻击),是一个新的攻击手法。具体的情况老李也找到了相关的介绍,下面就分享给大…...

分布式事务解决方案——TCC

TCC是Try、Confirm、Cancel三个词语的缩写&#xff0c;TCC要求每个分支事务实现三个操作&#xff1a;预处理Try、确认Confirm、撤销Cancel。1、Try 阶段是做业务检查(一致性)及资源预留(隔离)&#xff0c;此阶段仅是一个初步操作&#xff0c;它和后续的Confirm一起才能真正构成…...

ITSS认证分为几个级别,哪个级别最高

​一、什么是ITSS ITSS( 信息技术服务标准&#xff0c;简称ITSS)是国内第一套成体系和综合配套的信息技术服务标准库&#xff0c;全面规范了IT服务产品及其组成要素&#xff0c;用于指导实施标准化和可信赖的IT服务。 ITSS是在工业和信息化部、国家标准化管理委员会的联合指导下…...

ZigBee案例笔记 - USART

文章目录1.串行通信接口简述2.串行通信接口寄存器U0CSR (0x86) -USART 0 控制和状态U0UCR (0xC4)–USART 0 UART 控制U0GCR (0xC5)–USART 0 通用控制U0BUF (0xC1) – USART 0 接收/传送数据缓存U0BAUD (0xC2) – USART 0 波特率控制3.设置串行通信接口比特率控制寄存器4.外设I…...

java | 基于Redis的分布式锁实现①

前言 首先&#xff0c;为了确保分布式锁可用&#xff0c;我们至少要确保锁的实现同时满足以下四个条件&#xff1a; 互斥性。在任意时刻&#xff0c;只有一个客户端能持有锁。不会发生死锁。即使有一个客户端在持有锁的期间崩溃而没有主动解锁&#xff0c;也能保证后续其他客户…...

十六、基于FPGA的CRC校验设计实现

1&#xff0c;CRC校验循环冗余校验&#xff08;Cyclic Redundancy Check&#xff0c; CRC&#xff09;是一种根据网络数据包或计算机文件等数据产生简短固定位数校验码的一种信道编码技术&#xff0c;主要用来检测或校验数据传输或者保存后可能出现的错误。它是利用除法及余数的…...

2022爱分析 · DataOps厂商全景报告 | 爱分析报告

报告编委 李喆 爱分析合伙人&首席分析师 廖耘加 爱分析分析师 目录 1. 研究范围定义 2. 市场洞察 3. 厂商全景地图 4. 市场分析与厂商评估 5. 入选厂商列表 1. 研究范围定义 研究范围 在后疫情时代&#xff0c;以数据分析为代表的数据消费场景日益丰富&…...

京东前端react面试题及答案

useEffect 与 useLayoutEffect 的区别 &#xff08;1&#xff09;共同点 运用效果&#xff1a; useEffect 与 useLayoutEffect 两者都是用于处理副作用&#xff0c;这些副作用包括改变 DOM、设置订阅、操作定时器等。在函数组件内部操作副作用是不被允许的&#xff0c;所以需…...

TongWeb8数据源相关问题

问题一&#xff1a;数据源连接不足当TongWeb数据源连接用完时&#xff0c;除了监控中看到连接占用高以外&#xff0c;日志中会有如下提示信息。2023-02-14 10:24:43 [WARN] - com.tongweb.web.jdbc.pool.PoolExhaustedException: [TW-0.0.0.0-8088-3] Timeout: Pool empty. Una…...

关于最近大热的AI,你怎么看?

AI人工智能&#xff0c;相信大家都不陌生&#xff0c;也都接触过不少。但是最近小编在网上冲浪的时候发现各大媒体又掀起了一阵AI热潮&#xff0c;AI不是很常见了吗&#xff1f;是又有什么新的发展吗&#xff1f; 带着强烈的好奇心&#xff0c;我在地铁上读完了一篇关于Chatgp…...

25.架构和软件产品线

文章目录25 Architecture and Software Product Lines架构和软件产品线25.1 An Example of Product Line Variability 产品线可变性的一个例子25.2 What Makes a Software Product Line Work? 软件产品线的工作原理是什么&#xff1f;25.3 Product Line Scope 产品线范围25.4 …...

Seata-server 源码学习(一)

Seata源码学习引入 学习了Seata的应用以后&#xff0c;我们从这开始要开始分析Seata的源码相关内容 源码下载 官方地址&#xff1a;https://seata.io/zh-cn/blog/download.html 通过idea打开seata-1.4.2版本的源码 回顾AT模式 其实在之前的应用课程中&#xff0c;我们已经用…...

2023新华为OD机试题 - 斗地主(JavaScript)

斗地主 题目 斗地主起源于湖北十堰房县, 据传是一位叫吴修全的年轻人根据当地流行的扑克玩法“跑得快”改编的, 如今已风靡整个中国,并流行于互联网上 牌型: 单顺,又称顺子,最少5张牌,最多12张牌(3...A),不能有2, 也不能有大小王,不计花色 例如:3-4-5-7-8,7-8-9-1…...

素数相关(结合回文数,合数)线性筛素数(欧拉筛法)Euler【算法模板笔记】

一、朴素筛法&#xff08;埃拉托斯特尼筛法&#xff09;Eratosthenes 筛法&#xff08;埃拉托斯特尼筛法&#xff0c;简称埃氏筛法&#xff09;时间复杂度是O(nloglogn)不常用&#xff0c;被欧拉筛代替&#xff0c;略二、线性筛素数&#xff08;欧拉筛法&#xff09;简介线性筛…...

推挽电路与图腾柱结构技术解析与应用

图腾柱与互补推挽电路的技术解析1. 推挽电路基础概念1.1 推挽电路基本原理推挽电路(Push-Pull)是一种功率放大电路结构&#xff0c;其核心设计思想是通过两个互补工作的晶体管交替导通&#xff0c;实现对输入信号的功率放大。典型推挽电路具有以下两个关键特性&#xff1a;强大…...

嵌入式Linux无线AP模式实现与配置详解

1. 嵌入式Linux设备无线AP模式实现方案1.1 系统概述本方案实现了一种基于嵌入式Linux系统的无线接入点(AP)配置方法&#xff0c;可将废旧开发板改造为无线调试终端。该系统主要解决以下两个工程需求&#xff1a;AP配网功能&#xff1a;实现智能硬件设备的热点配网模式&#xff…...

AWPortrait-Z人像美化效果展示:科哥版WebUI实测,让普通人像变专业级

AWPortrait-Z人像美化效果展示&#xff1a;科哥版WebUI实测&#xff0c;让普通人像变专业级 1. 效果总览&#xff1a;从普通到专业的蜕变 1.1 什么是真正的人像美化&#xff1f; 传统美颜软件往往采用"一刀切"的处理方式&#xff1a;过度磨皮、夸张大眼、强行瘦脸…...

零基础入门:ComfyUI工作流详解,手把手教你修复泛黄老照片

零基础入门&#xff1a;ComfyUI工作流详解&#xff0c;手把手教你修复泛黄老照片 翻开泛黄的老照片&#xff0c;那些模糊的轮廓和褪色的记忆总让人心生遗憾。如今&#xff0c;借助ComfyUI这一强大的AI工具&#xff0c;即使没有任何技术背景&#xff0c;你也能轻松让这些珍贵影像…...

Windows Defender禁用技术深度解析:通过WSC API实现安全控制

Windows Defender禁用技术深度解析&#xff1a;通过WSC API实现安全控制 【免费下载链接】no-defender A slightly more fun way to disable windows defender. (through the WSC api) 项目地址: https://gitcode.com/GitHub_Trending/no/no-defender Windows Defender作…...

18-AI论文创作:自动找参考文献并精准标注

示例 薛磊.组织学习、数字能力与组织敏捷性的关系研究[D].吉林大学,2024. https://link.cnki.net/doi/10.27162/d.cnki.gjlin.2024.001308 关键词&#xff1a; 数字技术 组织学习 AI实战 使用大模型“探索” 请找到这这段话的内容向匹配的参考文献&#xff0c;并以&#xff…...

Win11Debloat开源工具深度解析:从系统诊断到性能优化的完整实践

Win11Debloat开源工具深度解析&#xff1a;从系统诊断到性能优化的完整实践 【免费下载链接】Win11Debloat 一个简单的PowerShell脚本&#xff0c;用于从Windows中移除预装的无用软件&#xff0c;禁用遥测&#xff0c;从Windows搜索中移除Bing&#xff0c;以及执行各种其他更改…...

FDTD远场投影避坑指南:从monitor设置到farfield3d参数优化

FDTD远场投影避坑指南&#xff1a;从monitor设置到farfield3d参数优化 在光学和电磁场仿真中&#xff0c;远场分析是评估器件性能的关键环节。FDTD Solutions作为一款强大的时域有限差分法仿真工具&#xff0c;其farfield3d功能能够将近场数据转换为远场分布&#xff0c;为天线…...

STM32F1轻量USB复合设备库:HID+MIDI+MSC一体化实现

1. 项目概述USBComposite for STM32F1 是一个面向 STM32F1 系列微控制器&#xff08;基于 ARM Cortex-M3 内核&#xff09;的轻量级、可裁剪式 USB 复合设备固件库。其核心目标是在资源受限的 F1 平台&#xff08;典型 Flash ≤ 64KB&#xff0c;SRAM ≤ 20KB&#xff09;上&am…...

3个创意突破:GitHub推荐项目精选的算法艺术与Canvas设计实践指南

3个创意突破&#xff1a;GitHub推荐项目精选的算法艺术与Canvas设计实践指南 【免费下载链接】skills 本仓库包含的技能展示了Claude技能系统的潜力。这些技能涵盖从创意应用到技术任务、再到企业工作流。 项目地址: https://gitcode.com/GitHub_Trending/skills3/skills …...