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

LeetCode 热题100(八)【二叉树】(3)

目录

8.11二叉树展开为链表(中等)

8.12从前序与中序遍历序列构造二叉树(中等)

8.13路径总和III(中等)

8.14二叉树的最近公共祖先(中等)

8.15二叉树中的最大路径和(困难)

8.11二叉树展开为链表(中等)

题目描述:leetcode链接 114. 二叉树展开为链表

给你二叉树的根结点 root ,请你将它展开为一个单链表:

  • 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1:

输入:root = [1,2,5,3,4,null,6]
输出:[1,null,2,null,3,null,4,null,5,null,6]

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [0]
输出:[0]

思路:

1.将左、右子树分别变为链表L和R

2.根节点的右节点变为L的根节点,根节点的左节点为空

3.L尾节点的右节点变为R的根节点

举例说明:

见上图

代码:

class Solution {
public:void flatten(TreeNode* root) {if (!root) return;flatten(root -> left);flatten(root -> right);TreeNode* temp = root -> right;root -> right = root -> left;root -> left = nullptr;while(root -> right) root = root -> right;root -> right = temp;}
};

8.12从前序与中序遍历序列构造二叉树(中等)

题目描述:leetcode链接 105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

思路:

1.由于前序遍历的顺序是【根-左子树-右子树】,中序遍历的顺序是【左子树-根-右子树】,所以由上图的前序遍历preorder可知,它的第一个元素3为根节点。那么由中序遍历inorder可知根节点3的左侧元素为左子树,共1个元素;根节点3的右侧元素为右子树,共3个元素。

2.记录3的左子树的前序遍历顺序和中序遍历顺序,其中9即为3的左节点

记录3的右子树的前序遍历顺序和中序遍历顺序,其中20即为3的右节点

3.记录20的左子树的前序遍历顺序和中序遍历顺序,其中15即为20的左节点

记录20的右子树的前序遍历顺序和中序遍历顺序,其中7即为20的右节点

举例说明:

见上图

代码:

class Solution {
public:unordered_map<int, int> mp;TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int n = preorder.size();for (int i = 0; i < n; i++) {mp[inorder[i]] = i;}return build(preorder, inorder, 0, n - 1, 0, n - 1);}TreeNode* build(vector<int>& preorder, vector<int>& inorder, int pre_l, int pre_r, int in_l, int in_r) {if (pre_l > pre_r) return nullptr;//前序遍历中的根节点位置int pre_root = pre_l;//中序遍历中的根节点位置int in_root = mp[preorder[pre_root]];TreeNode* root = new TreeNode(preorder[pre_root]);//左子树节点个数int size_l = in_root - in_l;//构造左右子树root -> left = build(preorder, inorder, pre_root + 1, pre_root + size_l, in_l, in_root - 1);root -> right = build(preorder, inorder, pre_root + size_l + 1, pre_r, in_root + 1, in_r);return root;}
};

8.13路径总和III(中等)

题目描述:leetcode链接 437. 路径总和 III

给定一个二叉树的根节点 root ,和一个整数 targetSum ,求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。

示例 1:

输入:root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出:3
解释:和等于 8 的路径有 3 条,如图所示。

示例 2:

输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出:3

思路:

        和560. 和为K的子数组类似,使用前缀和+哈希表的方式来解决,只不过我们现在面对的数据是存储在二叉树里面了

注:unordered_map<long, int> mp和long sum的类型为long,要不然有几个测试用例通过不了

举例说明:

代码:

class Solution {
public:int ans = 0;unordered_map<long, int> mp;int pathSum(TreeNode* root, int targetSum) {mp[0] = 1;dfs(root, targetSum, 0);return ans;}void dfs(TreeNode* root, int targetSum, long sum) {if (!root) return;sum += root -> val;if (mp.find(sum - targetSum) != mp.end()) ans += mp[sum - targetSum];mp[sum]++;dfs(root -> left, targetSum, sum);dfs(root -> right, targetSum, sum);mp[sum]--;}
};

8.14二叉树的最近公共祖先(中等)

题目描述:leetcode链接 236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

示例 1:

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出:3
解释:节点5和节点1的最近公共祖先是节点3

示例 2:

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出:5
解释:节点5和节点4的最近公共祖先是节点5。因为根据定义最近公共祖先节点可以为节点本身。

示例 3:

输入:root = [1,2], p = 1, q = 2
输出:1

思路:

        按照p、q中一节点是否是另一节点的祖先节点可以分为上图两种情况 。

        使用递归,分以下几种情况讨论:

1.如果当前节点为空,或者等于p,或者等于q,返回当前节点

2.如果当前节点左、右子树均不返回空,返回当前节点

3.如果当前节点左子树返回不为空,右子树为空,返回左子树递归结果

4.如果当前节点右子树返回不为空,左子树为空,返回右子树递归结果

5.如果当前节点左、右子树均返回空,返回空

举例说明:

代码:

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (!root || root == p || root == q) {return root;}TreeNode* L = lowestCommonAncestor(root -> left, p, q);TreeNode* R = lowestCommonAncestor(root -> right, p, q);if (L && R) return root;return L ? L : R;}
};

8.15二叉树中的最大路径和(困难)

题目描述:leetcode链接 199. 二叉树中的最大路径和

二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ,返回其 最大路径和 。

示例 1:

输入:root = [1,2,3]
输出:6
解释:最优路径是 2 -> 1 -> 3 ,路径和为 2 + 1 + 3 = 6

示例 2:

输入:root = [-10,9,20,null,null,15,7]
输出:42
解释:最优路径是 15 -> 20 -> 7 ,路径和为 15 + 20 + 7 = 42

思路:

1.定义一个函数getNum(TreeNode* root),可以计算root节点的贡献值

贡献值可以理解为以该节点为起点,在其子树中寻找一条路径,使其路径和最大

对空节点而言,getNum(NULL)=0

2.以下图为例,

根节点-10的路径和ans(-10)= -10+max(getNum(15), 0)+max(getNum(-5), 0)

遍历所有节点,其中ans的最大值即为二叉树的最大路径和

举例说明:

代码:

class Solution {
public:int ans = INT_MIN;int maxPathSum(TreeNode* root) {getNum(root);return ans;}int getNum(TreeNode* root){if (!root) return 0;int L = max(getNum(root -> left), 0);int R = max(getNum(root -> right), 0);ans = max(ans, root -> val + L + R);return root -> val + max(L, R);}
};

相关文章:

LeetCode 热题100(八)【二叉树】(3)

目录 8.11二叉树展开为链表&#xff08;中等&#xff09; 8.12从前序与中序遍历序列构造二叉树&#xff08;中等&#xff09; 8.13路径总和III&#xff08;中等&#xff09; 8.14二叉树的最近公共祖先&#xff08;中等&#xff09; 8.15二叉树中的最大路径和&#xff08;困…...

uniapp h5实现录音

使用npm安装 npm install recorder-core引入Recorder库 可以使用import、require、html script等你适合的方式来引入js文件&#xff0c;下面的以import为主要参考&#xff0c;其他引入方式根据文件路径自行调整一下就可以了。 //必须引入的Recorder核心&#xff08;文件路径是…...

字节跳动Android面试题汇总及参考答案(80+面试题,持续更新)

Android 四大组件是什么? Android 四大组件分别是 Activity、Service、Broadcast Receiver 和 Content Provider。 Activity 是 Android 应用中最基本的组件,用于实现用户界面。它可以包含各种视图控件,如按钮、文本框等。一个 Activity 通常对应一个屏幕的内容。用户可以通…...

【go从零单排】通道select、通道timeout、Non-Blocking Channel Operations非阻塞通道操作

&#x1f308;Don’t worry , just coding! 内耗与overthinking只会削弱你的精力&#xff0c;虚度你的光阴&#xff0c;每天迈出一小步&#xff0c;回头时发现已经走了很远。 &#x1f4d7;概念 select 语句是 Go 的一种控制结构&#xff0c;用于等待多个通道操作。它类似于 s…...

PSRR仿真笔记

1.首先打开bandgap的testbench电路&#xff0c;选择schematic 2.打开电路后,选择VDD模块&#xff0c;然后按键盘Q&#xff0c;进行编辑&#xff0c;将AC magnitude改为1 V 3.修改完成后&#xff0c;点击左上角Launch > ADE Explorer 4.在出现的窗口中&#xff0c;选择Creat…...

AUTOSAR_EXP_ARAComAPI的7章笔记(3)

☞返回总目录 相关总结&#xff1a;AutoSar AP简单多绑定总结 7.3 多绑定 如在 5.4.3 小节中简要讨论的&#xff0c;某个代理类 / 骨架类的不同实例之间的技术传输是不同的&#xff0c;多绑定描述了这种情况的解决方案。多种技术原因都可能导致这种情况出现&#xff1a; 代…...

WSADATA 关键字详细介绍

WSADATA 是 Windows Sockets API&#xff08;Winsock&#xff09;中用于存储 Winsock 库的初始化信息的结构体。在使用 Winsock API 之前&#xff0c;必须通过调用 WSAStartup() 函数进行初始化&#xff0c;WSADATA 结构体用于接收有关 Winsock 库版本的信息。Winsock 是 Windo…...

Day44 | 动态规划 :状态机DP 买卖股票的最佳时机IV买卖股票的最佳时机III

Day44 | 动态规划 &#xff1a;状态机DP 买卖股票的最佳时机IV&&买卖股票的最佳时机III&&309.买卖股票的最佳时机含冷冻期 动态规划应该如何学习&#xff1f;-CSDN博客 本次题解参考自灵神的做法&#xff0c;大家也多多支持灵神的题解 买卖股票的最佳时机【…...

Area-Composition模型部署指南

一、介绍 本模型可以通过输入不同的提示词&#xff0c;然后根据各部分提示词进行融合生成图片。如下图&#xff1a; 此图像包含 4 个不同的区域&#xff1a;夜晚、傍晚、白天、早晨 二、部署 环境要求&#xff1a; 最低显存&#xff1a;10G 1. 部署ComfyUI 本篇的模型部署…...

策略模式、状态机详细解读

策略模式 (Strategy Pattern) 策略模式 (Strategy Pattern) 是一种行为型设计模式&#xff0c;旨在将一组算法封装成独立的类&#xff0c;使得它们可以相互替换。这种模式让算法的变化不会影响到使用算法的客户&#xff0c;减少了类之间的耦合。策略模式通常用于处理一类问题&…...

OpenWrt广播DNS到客户端

OpenWrt广播DNS到客户端 Network -> Interfaces -> lan ->DHCP Server -> Advanced Settings -> DHCP-Options 设置 6,dns1,dns2 如下图 也可以直接编辑 /etc/config/dhcp config dhcp lan list dhcp_option 6,119.29.29.29,223.5.5.5 #ipv4 option dns 2402:4…...

C++编程技巧与规范-类和对象

类和对象 1. 静态对象的探讨与全局对象的构造顺序 静态对象的探讨 类中的静态成员变量(类类型静态成员) 类中静态变量的声明与定义&#xff08;类中声明类外定义&#xff09; #include<iostream> using namespace std;namespace _nmspl {class A{public:A():m_i(5){…...

AutoHotKey自动热键AHK-正则表达式

在这个软件的操作中,基本都是需要即时的解决一些问题,所以对字符串的操作是比较多的,所以正则的使用还是比较重要的,接下来我们用一个例子来了解正则表达式的使用 str "7654321" RegExMatch(str, "65(43)(21)", SubPat)str ( str %str% SubPat %SubPa…...

【3D Slicer】的小白入门使用指南四

开源解剖影像浏览工具Open Anatomy Browser使用及介绍 和3D slicer米有太大关系,该工具是网页版影像数据的浏览工具(可以简单理解为网页版的3D slicer) 介绍 ● 开放解剖(OA)浏览器是由神经影像分析中心开发的,基于网络浏览器技术构建的图谱查看器。 ● OA浏览器将解剖模…...

flink同步mysql数据表到pg库

1.关闭防火墙和selinux systemctl stop firewalld systemctl disable firewalld systemctl status firewalldvi /etc/selinux/config 修改为disabled2.安装java8 yum list java-1.8* yum install java-1.8.0-openjdk* -yjava -version3.下载和部署postgresql 下载地址&#…...

AndroidStudio-常用布局

一、线性布局LinearLayout 线性布局内部的各视图有两种排列方式: 1.orientation属性值为horizontal时&#xff0c;内部视图在水平方向从左往右排列。 2.orientation属性值为vertical时&#xff0c;内部视图在垂直方向从上往下排列。 如果不指定orientation属性&#xff0c;…...

Vue全栈开发旅游网项目(10)-用户管理后端接口开发

1.异步用户登录\登出接口开发 1.设计公共响应数据类型 文件地址&#xff1a;utils/response404.py from django.http import JsonResponseclass BadRequestJsonResponse(JsonResponse):status_code 400def __init__(self, err_list, *args, **kwargs):data {"error_c…...

[Android]查找java类中声明为native方法的具体实现方法

在android代码中&#xff0c;经常可以看到native方法&#xff0c;需要查看其对应的C方法&#xff0c;这些方法是一一对应的&#xff0c;对应关系是在jni注册里关联起来的。 比较直观的是这样的例子&#xff0c; Parcel.java //Java层的方法里调用了native方法nativeWriteInt…...

Exploring Defeasible Reasoning in Large Language Models: A Chain-of-Thought A

文章目录 题目摘要简介准备工作数据集生成方法实验结论 题目 探索大型语言模型中的可废止推理&#xff1a;思路链 论文地址&#xff1a;http://collegepublications.co.uk/downloads/LNGAI00004.pdf#page136 摘要 许多大型语言模型 (LLM) 经过大量高质量数据语料库的训练&…...

uniapp在app模式下组件传值

在 UniApp 编译成 App 后&#xff0c;传递参数可以通过多种方式实现&#xff0c;常见的方式有以下几种&#xff1a; 1. 通过 URL 参数传递&#xff08;适用于 WebView&#xff09; 如果你的 App 页面通过 WebView 渲染&#xff0c;可以像在 Web 端一样通过 URL 传递参数。例如…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

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

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

Kafka入门-生产者

生产者 生产者发送流程&#xff1a; 延迟时间为0ms时&#xff0c;也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于&#xff1a;异步发送不需要等待结果&#xff0c;同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...