当前位置: 首页 > 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;简介线性筛…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

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* …...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

JS手写代码篇----使用Promise封装AJAX请求

15、使用Promise封装AJAX请求 promise就有reject和resolve了&#xff0c;就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程

STM32F1 本教程使用零知标准板&#xff08;STM32F103RBT6&#xff09;通过I2C驱动ICM20948九轴传感器&#xff0c;实现姿态解算&#xff0c;并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化&#xff0c;适合嵌入式及物联网开发者。在基础驱动上新增…...