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

day018 第六章 二叉树 part05

一、513.找树左下角的值

这个题目的主要思路是使用广度优先搜索(BFS)遍历整棵树,最后返回最后一层的最左边的节点的值。具体的实现可以使用队列来存储每一层的节点,并且在遍历每一层节点时,不断更新最左边的节点的值。时间复杂度为O(n),其中n是节点的个数。

二、112.路径总和

这个题目的主要思路是使用深度优先搜索(DFS)遍历整棵树,同时记录到达每个节点时的路径和,如果到达叶子节点时路径和等于给定的目标和,则返回true。具体的实现可以使用递归来实现DFS,同时在每个节点处更新路径和,并且在到达叶子节点时判断路径和是否等于目标和。时间复杂度为O(n),其中n是节点的个数。

三、113.路径总和ii

这个题目的主要思路和112题类似,也是使用DFS遍历整棵树,同时记录到达每个节点时的路径和,并且在到达叶子节点时判断路径和是否等于给定的目标和。不同的是,这个题目需要返回所有满足条件的路径,而不仅仅是返回true或false。具体的实现可以在DFS的过程中使用一个数组来存储当前的路径,并且在到达叶子节点时,如果路径和等于目标和,则将整个路径加入结果列表中。时间复杂度为O(n^2),其中n是节点的个数,主要是因为每次需要复制一份路径数组。

四、106.从中序与后序遍历序列构造二叉树

这个题目的主要思路是使用递归来构建整棵树。具体的实现可以先找到后序遍历序列中的最后一个节点作为根节点,然后在中序遍历序列中找到根节点的位置,从而确定左子树和右子树的范围。然后递归的构建左子树和右子树即可。时间复杂度为O(n),其中n是节点的个数。

五、105.从前序与中序遍历序列构造二叉树

这个题目的主要思路和106题类似,也是使用递归来构建整棵树。具体的实现可以先找到前序遍历序列中的第一个节点作为根节点,然后在中序遍历序列中找到根节点的位置,从而确定左子树和右子树的范围。然后递归的构建左子树和右子树即可。时间复杂度为O(n),其中n是节点的个数。

一、513.找树左下角的值

public int findBottomLeftValue(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int res = root.val;while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();if (i == 0) {res = node.val;}if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}}return res;
}

二、112.路径总和

public boolean hasPathSum(TreeNode root, int sum) {if (root == null) {return false;}if (root.left == null && root.right == null) {return sum == root.val;}return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}

三、113.路径总和ii

public List<List<Integer>> pathSum(TreeNode root, int sum) {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();dfs(root, sum, path, res);return res;
}private void dfs(TreeNode root, int sum, List<Integer> path, List<List<Integer>> res) {if (root == null) {return;}path.add(root.val);if (root.left == null && root.right == null && sum == root.val) {res.add(new ArrayList<>(path));}dfs(root.left, sum - root.val, path, res);dfs(root.right, sum - root.val, path, res);path.remove(path.size() - 1);
}

四、106.从中序与后序遍历序列构造二叉树

public TreeNode buildTree(int[] inorder, int[] postorder) {if (inorder == null || postorder == null || inorder.length != postorder.length) {return null;}int n = inorder.length;Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < n; i++) {map.put(inorder[i], i);}return buildTree(inorder, 0, n - 1, postorder, 0, n - 1, map);
}private TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd, Map<Integer, Integer> map) {if (inStart > inEnd || postStart > postEnd) {return null;}int rootVal = postorder[postEnd];TreeNode root = new TreeNode(rootVal);int index = map.get(rootVal);int leftSize = index - inStart;root.left = buildTree(inorder, inStart, index - 1, postorder, postStart, postStart + leftSize - 1, map);root.right = buildTree(inorder, index + 1, inEnd, postorder, postStart + leftSize, postEnd - 1, map);return root;
}

五、105.从前序与中序遍历序列构造二叉树

public TreeNode buildTree(int[] preorder, int[] inorder) {if (preorder == null || inorder == null || preorder.length != inorder.length) {return null;}int n = preorder.length;Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < n; i++) {map.put(inorder[i], i);}return buildTree(preorder, 0, n - 1, inorder, 0, n - 1, map);
}private TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> map) {if (preStart > preEnd || inStart > inEnd) {return null;}int rootVal = preorder[preStart];TreeNode root = new TreeNode(rootVal);int index = map.get(rootVal);int leftSize = index - inStart;root.left = buildTree(preorder, preStart + 1, preStart + leftSize, inorder, inStart, index - 1, map);root.right = buildTree(preorder, preStart + leftSize + 1, preEnd, inorder, index + 1, inEnd, map);return root;
}

相关文章:

day018 第六章 二叉树 part05

一、513.找树左下角的值 这个题目的主要思路是使用广度优先搜索&#xff08;BFS&#xff09;遍历整棵树&#xff0c;最后返回最后一层的最左边的节点的值。具体的实现可以使用队列来存储每一层的节点&#xff0c;并且在遍历每一层节点时&#xff0c;不断更新最左边的节点的值。…...

如何下载ChatGPT-ChatGPT如何写作

CHATGPT能否改一下文章 ChatGPT 作为一种自然语言处理技术&#xff0c;生成的文章可能存在表达不够准确或文风不符合要求等问题。在这种情况下&#xff0c;可以使用编辑和修改来改变输出的文章&#xff0c;使其符合特定的要求和期望。 具体来说&#xff0c;可以采用以下步骤对…...

微策略再次买入

原创&#xff1a;刘教链* * *隔夜&#xff0c;比特币再次小幅回升至28k上方。微策略&#xff08;Microstrategy&#xff09;创始人Michael Saylor发推表示&#xff0c;微策略再次出手&#xff0c;买入1045枚比特币。此次买入大概花费2930万美元&#xff0c;平均加仓成本28016美…...

express框架

Express 是基于 Node.js 平台&#xff0c;快速、开放、极简的 Web 开发框架. 创建一个基本的express web服务器 // 1.导入express const express require(express); // 2.创建web服务器 const app express(); // 3.启动web服务器 app.listen(80, ()>{console.log(expres…...

完蛋的goals

...

Javase学习文档------面象对象初探

引入面向对象 面向对象的由来: 面向对象编程&#xff08;Object-Oriented Programming, OOP&#xff09;是一种编程范型&#xff0c;其由来可以追溯到20世纪60年代。在此之前&#xff0c;主流编程语言采用的是“过程化编程”模式&#xff0c;即面向过程编程模式。在这种模式下&…...

ChatGPT能够干翻谷歌吗?

目前大多数人对于ChatGPT的喜爱&#xff0c;主要源自于其强大的沟通能力&#xff0c;当我们向ChatGPT提出问题时&#xff0c;它不仅能够为我们提供结论&#xff0c;而且还能够与我们建立沟通&#xff0c;向ChatGPT提出任何问题&#xff0c;感觉都像是在与一个真实的人类进行交谈…...

PCL 使用点云创建数字高程模型DEM

目录 一、DEM1、数字高程模型二、代码实现三、结果展示1、点云2、DEM四、相关链接一、DEM 1、数字高程模型 数字高程模型(Digital Elevation Model),简称DEM,是通过有限的地形高程数据实现对地面地形的数字化模拟(即地形表面形态的数字化表达),它是用一组有序数值阵列形…...

我体验了首个接入GPT-4的代码编辑器,太炸裂了

最近一款名为Cursor的代码编辑器已经传遍了圈内&#xff0c;受到众多编程爱好者的追捧。 它主打的亮点就是&#xff0c;通过 GPT-4 来辅助你编程&#xff0c;完成 AI 智能生成代码、修改 Bug、生成测试等操作。 确实很吸引人&#xff0c;而且貌似也能大大节省人为的重复工作&…...

互联网数据挖掘与分析讲解

一、定义 数据挖掘&#xff08;英语&#xff1a;Data mining&#xff09;&#xff0c;又译为资料探勘、数据采矿。它是数据库知识发现&#xff08;英语&#xff1a;Knowledge-Discovery in Databases&#xff0c;简称&#xff1a;KDD)中的一个步骤。数据挖掘一般是指从大量的数…...

linux之cut的使用

cut是一个选取命令&#xff0c;就是将一段数据经过分析&#xff0c;取出我们想要的。一般来说&#xff0c;选取信息通常是针对“行”来进行分析的&#xff0c;并不是整篇信息分析的 其语法格式为&#xff1a; cut [-bn] [file] 或 cut [-c][file] 或 cut [-df] [file]使用说明:…...

Redis第十讲 Redis之Hash数据结构Dict-rehash扩容操作

Rehash 执行过程 字典的 rehash 操作实际上就是执行以下任务: 创建一个比 ht[0]->table 更大的 ht[1]->table ;将 ht[0]->table 中的所有键值对迁移到 ht[1]->table ;将原有 ht[0] 的数据清空,并将 ht[1] 替换为新的 ht[0] ; 经过以上步骤之后, 程序就在不改…...

电动力学问题中的Matlab可视化

电磁场的经典描述 小说一则 电磁场的经典描述就是没有啥玩意量子力学的经典电动力学下对电磁场的描述,以后有空写个科幻小说,写啥呢,就写有天张三遇见了一个外星人,外星人来自这样一个星球,星球上的物质密度特别低,导致外星人的测量会明显的影响物质的运动,外星人不能同时得到…...

云原生周刊:编程即将终结?

近日哈佛大学计算机科学的前教授 Matt Welsh&#xff0c;分享了他对计算机科学、分布式计算的未来以及 ChatGPT 和 GitHub Copilot 是否代表编程结束的开始的看法。 威尔士说&#xff0c;编程语言仍然很复杂。再多的工作也无法让它变得简单。 “在我看来&#xff0c;任何改进…...

C++ STL,resize 和 reserve 的区别

结论放前边&#xff1a;resize和reserve都可以给容器扩容&#xff0c;区别在于resize会进行填充&#xff0c;使容器处于满员的状态&#xff0c;即sizecapacity&#xff0c;而reserve不会填充&#xff0c;有size<capacity. 1. size 和 capacity 的区别 size和capacity是容器…...

Java——详解ReentrantLock与AQS的关联以及AQS的数据结构和同步状态State

前言 Java中大部分同步类&#xff08;Lock、Semaphore、ReentrantLock等&#xff09;都是基于AbstractQueuedSynchronizer&#xff08;简称为 AQS&#xff09;实现的。 AQS 是一种提供了原子式管理同步状态、阻塞和唤醒线程功能以及队列模型的简单框架。 本文会先介绍应用层&a…...

vue3+vite+ts 接入QQ登录

说明 前提资料准备 在QQ互联中心注册成为开发者 站点&#xff1a;https://connect.qq.com/创建应用&#xff0c;如图 js sdk方式 下载对应的sdk包 sdk下载&#xff1a;https://wiki.connect.qq.com/sdk%e4%b8%8b%e8%bd%bd 使用 下载离线js sdk 打开&#xff1a;https:…...

消息队列kafka及zookeeper机制

目录 一、zookeeper 1、zookeeper简介 2、zookeeper特点 3、zookeeper工作模式及机制 4、zookeeper应用场景及选举机制 5、zookeeper集群部署 ①实验环境 ②安装zookeeper 二、消息队列kafka 1、为什么要有消息队列 2、使用消息队列的好处 3、kafka简介 4、kafka…...

分布式 - 分布式体系架构:IT架构的演进过程

文章目录01. 应用与数据一体模式02. 应用服务和数据服务的分离03. 缓存与性能的提升04. 服务器集群处理并发05. 数据库读写分离06. 反向代理和 CDN07. 分布式文件系统和分布式数据库系统08. NoSQL和搜索引擎09. 业务拆分10. Redis缓存在应用服务器上是进程内缓存还是进程外缓存…...

CSDN 周赛42期

CSDN 周赛42期1、题目名称&#xff1a;鬼画符门之宗门大比2、题目名称&#xff1a;K皇把妹3、题目名称&#xff1a;影分身4、题目名称&#xff1a;开心的金明小结1、题目名称&#xff1a;鬼画符门之宗门大比 给定整数序列A。 求在整数序列A中连续权值最大的子序列的权值。 &…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

通过MicroSip配置自己的freeswitch服务器进行调试记录

之前用docker安装的freeswitch的&#xff0c;启动是正常的&#xff0c; 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...