leetcode - 257. 二叉树的所有路径
257. 二叉树的所有路径
题目
解决
做法一:深度优先搜索 + 回溯
深度优先搜索(Depth-First Search, DFS)是一种用于遍历或搜索树或图的算法。这种搜索方式会尽可能深地探索每个分支,直到无法继续深入为止,然后回溯到上一个节点,继续探索其他未访问的分支。
回溯我的个人理解是回退到之前的状态
大致想法:就是使用递归,在递归过程中使用 StringBuilder 存储路径上的节点和 箭头指向字符,直到 TreeNode 节点中左子节点 和 右子节点 都为空,将 StringBuilder 中存的依赖路径 加入到 list 中,每当退出递归,就回溯(将加入的 (节点值 + "->") 删除掉)
/*** 执行用时分布 5 ms 击败 30.20% 复杂度分析 消耗内存分布 41.53 MB 击败 70.56%*/
public List<String> binaryTreePaths(TreeNode root) {List<String> list = new ArrayList<>();StringBuilder path = new StringBuilder();path.append(root.val);// 递归获取 根节点到 叶子节点的路径getPath(root, path, list);return list;
}/*** 递归获取 根节点到 叶子节点的路径*/
public void getPath(TreeNode root, StringBuilder path, List<String> list) {// 递归边界就是 叶子节点,碰到叶子节点则递归结束,并将叶子节点的路径加入到结果集if (root.left == null && root.right == null){list.add(path.toString());return;}if (root.left != null){String pathStr = "->" + root.left.val;// 将 左子树节点的值加入到 树路径中path.append(pathStr);// 递归左子树getPath(root.left, path, list);// 回溯,将当前节点的左节点剔除出 字符串path.delete(path.length() - pathStr.length(), path.length());}if (root.right != null){String pathStr = "->" + root.right.val;path.append(pathStr);getPath(root.right, path, list);path.delete(path.length() - pathStr.length(), path.length());}
}
优化
做法上基本是这样,但是时间上呢还是太慢了,根据以往经验发现可以将字符串替换成 栈 这个数据结构,弹出一个节点,可比 StringBuilder 删除来得快,StringBuilder.delete 底层是将整个字符数组拷贝的,相比于 栈 他是先进后出的,从栈顶弹出元素相对较快。
Deque 参考链接:双端队列 【Deque】-CSDN博客
时间复杂度:O(nlogn);空间复杂度:O(nlogn)
因为遍历到叶子节点之后,还需要遍历 栈,最环的情况是 叶子节点的数量为 n/2,每个路径字符串的长度为 log(n)(因为完全二叉树的高度为 log(n))
/*** 执行用时分布 3 ms 击败 33.70% 复杂度分析 消耗内存分布 41.55 MB 击败 64.43%*/
public List<String> binaryTreePaths(TreeNode root) {List<String> list = new ArrayList<>();// 双端队列Deque<Integer> path = new LinkedList<>();// 递归获取 根节点到 叶子节点的路径getPath(root, path, list);return list;
}/*** 递归获取 根节点到 叶子节点的路径*/
public void getPath(TreeNode root, Deque<Integer> path, List<String> list) {if (root == null){return;}if (root.left == null && root.right == null){StringBuilder builder = new StringBuilder();// 遍历,组合成路径字符串path.forEach(val -> {builder.append(val).append("->");});// 加入当前叶子节点的 值builder.append(root.val);list.add(builder.toString());return;}// 因为回溯需要将,当前节点弹出并且需要按顺序循环遍历出来,所以选用 尾部插入,尾部弹出// 将当前节点加入path.add(root.val);// 递归左子树getPath(root.left, path, list);// 递归右子树getPath(root.right, path, list);// 回溯path.removeLast();
}
做法二:深度优先搜索
参考官解:. - 力扣(LeetCode)
这里相对于上面快,是因为这里不需要回溯,使用的是局部变量
/*** 参考官解:https://leetcode.cn/problems/binary-tree-paths/solutions/400326/er-cha-shu-de-suo-you-lu-jing-by-leetcode-solution/* 深度优先遍历解法* 执行用时分布 1 ms 击败 99.56% 复杂度分析 消耗内存分布 41.57 MB 击败 58.89%*/
public List<String> binaryTreePaths(TreeNode root) {List<String> list = new ArrayList<>();// 递归获取 根节点到 叶子节点的路径getPath(root, "", list);return list;
}/*** 递归获取 根节点到 叶子节点的路径*/
public void getPath(TreeNode root, String path, List<String> list) {if (root == null){return;}StringBuilder builder = new StringBuilder(path);builder.append(root.val);if (root.left == null && root.right == null){list.add(builder.toString());return;}builder.append("->");// 递归左子树getPath(root.left, builder.toString(), list);// 递归右子树getPath(root.right, builder.toString(), list);
}
做法三:广度优先遍历
广度优先遍历
广度优先遍历(Breadth-First Search, BFS)是一种用于图或树的遍历算法。这种搜索方式从根节点(或任意一个起始节点)开始,逐层访问每个节点的邻居节点,直到所有可达节点都被访问到。BFS 的特点是先访问离起点最近的节点,然后再逐步向外扩展。
/*** 宽度遍历/广度优先遍历* @param head*/
private static void levelOrder(Node head){if (head == null) {return;}Queue<Node> queue = new LinkedList<>();queue.offer(head);while (!queue.isEmpty()){head = queue.poll();System.out.print(head.value + " ");if (head.left != null){queue.offer(head.left);}if (head.right != null){queue.offer(head.right);}}
}
代码
/*** 广度优先搜索* 执行用时分布 2 ms 击败 47.70% 复杂度分析 消耗内存分布 41.48 MB 击败 79.08%*/
public List<String> binaryTreePaths(TreeNode root) {// 存储结果集List<String> result = new ArrayList<>();// 用于遍历存储节点Queue<TreeNode> nodeQueue = new LinkedList<>();// 用于存储 nodeQueue 的依赖路径Queue<String> pathQueue = new LinkedList<>();// 先将 根节点 加入队列用于遍历nodeQueue.add(root);// 将路径同步加入pathQueue.add(Integer.toString(root.val));// 遍历知道所有节点为空while (!nodeQueue.isEmpty()){// 弹出节点和路径TreeNode node = nodeQueue.poll();String path = pathQueue.poll();// 叶子节点if (node.left == null && node.right == null) {result.add(path);continue;}// 如果左子节点不为空就将节点加入到队列中,并将依赖路径拼接好加入队列if (node.left != null){nodeQueue.add(node.left);pathQueue.add(new StringBuilder(path).append("->").append(node.left.val).toString());}if (node.right != null){nodeQueue.add(node.right);pathQueue.add(new StringBuilder(path).append("->").append(node.right.val).toString());}}return result;
}
相关文章:

leetcode - 257. 二叉树的所有路径
257. 二叉树的所有路径 题目 解决 做法一:深度优先搜索 回溯 深度优先搜索(Depth-First Search, DFS)是一种用于遍历或搜索树或图的算法。这种搜索方式会尽可能深地探索每个分支,直到无法继续深入为止,然后回溯到上…...
python 相关
python 1. pip 安装某个版本范围的软件 pip install “elasticsearch>6,<7” pip install elasticsearchX.Y.Z 2. pip 查看包版本 pip show pandas 3. pip 下载whl包 https://tendcode.com/subject/article/pip-offline-download/ (更多平台与架构)pip downl…...

静态分析2:控制流分析(构建CFG)
参考:南京大学《软件分析》课程2 1、控制流分析 控制流分析实际上指的是构建控制流图(Control Flow Graph,CFG)CFG是静态分析的基础数据结构CFG的节点可以是单个指令、基本块(Basic Block,BB)…...
Linux 应用领域
目录 服务器领域 桌面环境 软件开发 数据分析与科学计算 嵌入式系统 虚拟化和云计算 人工智能与机器学习 物联网(IoT) 网络安全 服务器领域 Linux在服务器领域的应用是其最为广泛和成熟的领域之一。由于其开源、稳定、高效和安全的特性…...

FPM383C指纹模块超详解 附驱动
0. 本人使用环境介绍 0.1 硬件环境 ESP32-C3FPM383C指纹模块一根破旧的usb数据线 0.2 软件环境 Clion2024.2.2ESP-IDF5.3.1Clion插件ESP-IDF 1. 硬件接口说明 1.1 UART UART 缺省波特率为 57.6Kbps,数据格式:8 位数据位,2 位停止位&am…...

若依框架篇-若依集成 X-File-Storage 框架(实现图片上传阿里云 OSS 服务器)、EasyExcel 框架(实现 Excel 数据批量导入功能)
🔥博客主页: 【小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍ 文章目录 1.0 实现使用 Excel 文件批量导入 1.1 导入功能的前端具体实现 1.2 导入功能的后端具体实现 1.3 使用 EasyExcel 框架实现 Excel 读、写功能 1.4 将 Easy Excel 集成到…...

.rmallox勒索病毒肆虐:如何有效防范与应对
引言 在当今这个数字化时代,网络安全已成为一个不可忽视的重要议题。随着信息技术的飞速发展,网络空间的安全威胁也日益复杂多变。病毒、木马、勒索软件等恶意程序层出不穷,比如.rmallox勒索病毒。它们利用先进的技术手段,如代码…...
人工智能能否影响未来生活:一场深刻的社会与技术变革
随着人工智能技术的不断发展,我们已经目睹了它在各行各业掀起的巨大变革浪潮。从医疗行业的病例诊断、药物研发,到企业运营的数据分析、智能决策,再到日常生活中的智能语音助手、自动驾驶汽车、智能家居,人工智能正以前所未有的速…...

cmu 15-445学习笔记-3 存储引擎
03 Database Storage-Part Ⅰ 数据库存储上半部分 数据库分层划分结构图: Disk Manager:存储引擎,管理磁盘上的文件Bufferpool Manager:管理内存的缓存池Access Methods:访问方法Operator Execution:执行…...

[linux]和windows间传输命令scp 执行WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!错误解决
[linux]和windows间传输命令scp 执行WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!错误解决. 现象: 原因: 接收方服务器系统做了某些更改,导致登录时会报错。主要因为接收方服务器对登录过它的主机都会把该主机登录标识证书记录下来&a…...

C++ | Leetcode C++题解之第518题零钱兑换II
题目: 题解: class Solution { public:int change(int amount, vector<int>& coins) {vector<int> dp(amount 1), valid(amount 1);dp[0] 1;valid[0] 1;for (int& coin : coins) {for (int i coin; i < amount; i) {valid[…...
高并发-负载均衡
负载均衡在微服务架构中是一个重要的组成部分,旨在优化资源利用、提高服务可用性和确保系统的高可扩展性。以下是对微服务中的负载均衡的详细介绍,包括其原理、类型、实现方式以及相关的技术。 一、负载均衡的原理 负载均衡的基本原理是将进入系统的请…...

Docker 常用命令全解析:提升对雷池社区版的使用经验
Docker 常用命令解析 Docker 是一个开源的容器化平台,允许开发者将应用及其依赖打包到一个可移植的容器中。以下是一些常用的 Docker 命令及其解析,帮助您更好地使用 Docker。 1. Docker 基础命令 查看 Docker 版本 docker --version查看 Docker 运行…...

基于 Postman 和 Elasticsearch 测试乐观锁的操作流程
鱼说,你看不到我眼中的泪,因为我在水中。水说,我能感觉到你的泪,因为你在我心中。 -村上春树 在分布式系统中,多个并发操作对同一资源的修改可能导致数据不一致。为了解决这种问题,Elasticsearch 提供了乐观…...

如何从PPT中导出600dpi的高清图
Step1. 修改PPT注册表 具体过程,参见如下链接:修改ppt注册表,导出高分辨率图片 Step2. 打开PPT,找到自己想要保存的图,选中图像,查看图像尺寸并记录 Step3. 重新新建一个PPT,并根据记录的图片…...

day01-ElasticStack+Kibana
ElasticStack-数据库 #官网https://www.elastic.co/cn/ #下载7.17版环境准备 主机名IP系统版本VMware版本elk110.0.0.91Ubuntu 22.04.417.5.1elk210.0.0.92Ubuntu 22.04.417.5.1elk310.0.0.93Ubuntu 22.04.417.5.1 单机部署ES 1.下载ES软件包,放到/usr/local下 […...
HTML 约束验证
HTML5引入了表单相关的一些新机制:它为<input>元素和约束验证增加了一些新的语义类型,使得客户端检查表单内容变得容易。基本上,通过设置一些新的属性,常用的约束条件可以无需 JavaScript 代码而检测到;对于更复…...

vue3项目开发一些必备的内容,该安装安装,该创建创建
重新整理了一下项目开发必备的一些操作,以后直接复制黏贴运行,随着项目开发,后期会陆续补充常用插件或组件等 如果你是还没有安装过的新人,建议从《通过安装Element UI/Plus来学习vue之如何创建项目、搭建vue脚手架、npm下载、封装…...
2D拓扑图
2D拓扑图主要指的是在二维平面上表示物体形状和关系的一种图形表示方法。 一、基本概念 2D网格拓扑结构:在二维平面上,由一系列的节点(node)和边(edge)组成。每个节点代表一个具体的位置或坐标点…...
大数据面试题整理——Hive
系列文章目录 大数据面试题专栏点击进入 文章目录 系列文章目录Hive 面试知识点全面解析一、函数相关(一)函数分类与特点(二)concat和concat_ws的区别 二、SQL 的书写和执行顺序(一)书写顺序(二…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...
从面试角度回答Android中ContentProvider启动原理
Android中ContentProvider原理的面试角度解析,分为已启动和未启动两种场景: 一、ContentProvider已启动的情况 1. 核心流程 触发条件:当其他组件(如Activity、Service)通过ContentR…...

算法打卡第18天
从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。 示例 1: 输入:inorder [9,3,15,20,7…...

路由基础-路由表
本篇将会向读者介绍路由的基本概念。 前言 在一个典型的数据通信网络中,往往存在多个不同的IP网段,数据在不同的IP网段之间交互是需要借助三层设备的,这些设备具备路由能力,能够实现数据的跨网段转发。 路由是数据通信网络中最基…...
GeoServer发布PostgreSQL图层后WFS查询无主键字段
在使用 GeoServer(版本 2.22.2) 发布 PostgreSQL(PostGIS)中的表为地图服务时,常常会遇到一个小问题: WFS 查询中,主键字段(如 id)莫名其妙地消失了! 即使你在…...