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 的书写和执行顺序(一)书写顺序(二…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...

【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】
大家好,我是java1234_小锋老师,看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】,分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

C# 表达式和运算符(求值顺序)
求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如,已知表达式3*52,依照子表达式的求值顺序,有两种可能的结果,如图9-3所示。 如果乘法先执行,结果是17。如果5…...

R 语言科研绘图第 55 期 --- 网络图-聚类
在发表科研论文的过程中,科研绘图是必不可少的,一张好看的图形会是文章很大的加分项。 为了便于使用,本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中,获取方式: R 语言科研绘图模板 --- sciRplothttps://mp.…...