17_二叉树的所有路径

简介: 17_二叉树的所有路径

二叉树的所有路径

给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1:

输入:root = [1,2,3,null,5]
输出:["1->2->5","1->3"]

示例 2:

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

【思路】题目要求从根节点到叶子的路径,所以需要前序遍历,这样才方便让父节点指向孩子节点,找到对应的路径。本图涉及到回溯,因为我们要把路径记录下来,需要回溯来回退一个路径再进入另一个路径。

递归

1、递归函数参数以及返回值

要传入根节点,记录每一条路径的path,和存放结果集的result,这里递归不需要返回值,代码如下:

void traversal(TreeNode root, List<Integer> path, List<String> result)

2、确定递归终止条件

if (cur == null) {
  终止处理逻辑
}

本题只要找到叶子结点,就开始结束的处理逻辑了(把路径放进result里)。

那么什么时候算是找到了叶子结点呢?是当$cur!=null$,其左右孩子都为空的时候,就找到了叶子结点。所以本题的终止条件是:

if (cur.left == null && cur.right == null) {
  终止处理逻辑
}

3、确定单层递归逻辑

整体代码如下:(看代码可以大致理解,读流程太繁琐了)

递归+回溯

//递归法
class Solution {
    public List<String> binsryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();//存最终的结果
        if (root == null) {
            return res;
        }
        List<Integer> paths = new ArrayList<>();//作为结果中的路径
        traversal(root, paths, res);
        return res;
    }
    private void traversal(TreeNode root, List<Integer> pths, List<String> res) {
        paths.add(root.val);// 前序遍历,中
        //遇到叶子结点
        if (root.left == null && root.right == null) {
            //输出
            StringBuilder sb = new StringBuilder();//StringBuilder用来拼接字符串,速度更快
            for (int i = 0; i < path.size()-1; i++) {
                sb.append(paths.get(i)).append("->");
            }
            sb.sppend(paths.get(paths.size() - 1));  //记录最后一个节点
            res.add(sb.toString());  //收集一个路径
            return;
        }
        // 递归和回溯是同时进行,所以要放在同一个花括号里
        if (root.left != null) {
            traversal(root.left, paths, res);
            paths.remove(paths.size() - 1);//回溯
        }
        if (root.right != null) {  //右
            traversal(root.right, paths, res);
            paths.remove(paths.size() - 1);//回溯
        }
    }
}
//方法二
class Solution {
  List<String> result = new ArrayList<>();
  public List<String> binaryTreePaths(TreeNode root) {
    deal(root, "");
    return result;
  }
    public void deal(TreeNode node, String s) {
        if (node == null)
            return;
        if (node.left == null && node.right == null) {
            result.add(new StringBuilder(s).append(node.val).toString());
            return;
        }
        String tmp = new StringBuilder(s).append(node.val).append("->").toString();
        deal(node.left, tmp);
        deal(node.right, tmp);
    }
}
相关文章
|
负载均衡 应用服务中间件 持续交付
微服务架构下的Web服务器部署
【8月更文第28天】随着互联网应用的不断发展,传统的单体应用架构逐渐显露出其局限性,特别是在可扩展性和维护性方面。为了解决这些问题,微服务架构应运而生。微服务架构通过将应用程序分解成一系列小型、独立的服务来提高系统的灵活性和可维护性。本文将探讨如何在微服务架构中有效部署和管理Web服务器实例,并提供一些实际的代码示例。
517 0
|
7月前
|
自然语言处理 搜索推荐 前端开发
大模型联网搜索的短板与突破之路
本文作者详细分析了当前大模型在联网搜索功能中存在的几个主要问题,并提供了具体的案例和解决方案。
1014 8
大模型联网搜索的短板与突破之路
|
4月前
|
开发框架 定位技术 API
AgentScope 与 MCP:实践、思考与展望
AgentScope 作为一款功能强大的开源多智能体开发框架,为开发者提供了智能体构建、工具使用、多智能体编排等全方位支持。
532 37
|
Oracle 关系型数据库 MySQL
实时计算 Flink版操作报错之当将两个连接器放在同一个作业中时,MySQL作业无法启动,该怎么解决
在使用实时计算Flink版过程中,可能会遇到各种错误,了解这些错误的原因及解决方法对于高效排错至关重要。针对具体问题,查看Flink的日志是关键,它们通常会提供更详细的错误信息和堆栈跟踪,有助于定位问题。此外,Flink社区文档和官方论坛也是寻求帮助的好去处。以下是一些常见的操作报错及其可能的原因与解决策略。
|
11月前
|
机器学习/深度学习 人工智能 数据可视化
小滑块上个斜面,难倒多少高中生?现在,AI让它动起来了
《Augmented Physics:基于机器学习的物理学习工具》 高中物理学习中,小滑块上斜面等问题常让学生困惑。Augmented Physics利用AI技术,将静态物理图示转化为交互式模拟,通过增强实验、动画图示、双向操作和参数可视化等技术,帮助学生直观理解物理概念。研究表明,该工具能有效提升学生对物理概念的理解,具备广阔的应用前景。
202 1
|
机器学习/深度学习 并行计算 关系型数据库
【RetNet】论文解读:Retentive Network: A Successor to Transformer for Large Language Models
【RetNet】论文解读:Retentive Network: A Successor to Transformer for Large Language Models
443 1
|
数据采集 算法 物联网
【算法精讲系列】阿里云百炼SFT微调实践分享
本内容为您提供了百炼平台SFT微调的实践案例,帮助您方便并快速借助模型微调定制化您自己的专属模型。
3096 14
|
12月前
|
消息中间件 NoSQL Java
订单出现超时未关闭场景解决方案
订单出现超时未关闭场景解决方案
505 5
|
12月前
|
API 数据安全/隐私保护 开发者
商品详情 API 接口的调用次数是否有限制?
商品详情API接口调用次数受限,旨在保障系统稳定性和防止恶意攻击。平台依据账户类型设定不同限制:普通开发者账户调用次数较少,而企业级账户享有更高限额但需申请并可能收费。此外,平台还设置了短期和长期调用频率限制,以避免高并发请求导致服务器过载。
371 2
|
资源调度 搜索推荐 Shell
使用VitePress静态网站生成器创建组件库文档网站并部署到GitHub
本文介绍了如何使用 Vue3、TypeScript 和 Vite 开发组件库并将其发布到 npm。文章详细描述了安装依赖、配置项目、创建文档网站以及编写组件文档的步骤。通过使用 VitePress,可以轻松搭建组件库的文档站点,并实现 Algolia 搜索功能。此外,还提供了自动化脚本用于部署静态网站至 GitHub 以及发布组件库到 npm。最后,展示了完整的目录结构和网站效果。
487 1
使用VitePress静态网站生成器创建组件库文档网站并部署到GitHub