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);
    }
}
相关文章
|
算法 JavaScript 前端开发
开源项目推荐:CNC+CRC/SoftPLC/OpenCASCADE/CAD/CAM(三)
开源项目推荐:CNC+CRC/SoftPLC/OpenCASCADE/CAD/CAM
4557 1
开源项目推荐:CNC+CRC/SoftPLC/OpenCASCADE/CAD/CAM(三)
|
存储
【数据结构】连通图、连通分量与强连通图、强连通分量—区别在于强,强强在哪里?
【数据结构】连通图、连通分量与强连通图、强连通分量—区别在于强,强强在哪里?
12199 1
【数据结构】连通图、连通分量与强连通图、强连通分量—区别在于强,强强在哪里?
|
4月前
|
人工智能 安全 IDE
新版 阿里云 Qoder CN AI编程智能体功能介绍
在软件工程规模化迭代、全栈开发需求爆发的2026年,传统AI编码工具普遍存在功能单一、仅支持单行补全、无法理解整体工程架构、多文件联动薄弱、模型固化、团队规范难统一等问题,只能辅助简单代码编写,无法参与完整项目开发流程。为解决开发者编码效率低、工程迭代慢、重复工作量大、跨文件开发繁琐的痛点,阿里云完成**通义灵码品牌全面升级**,正式推出全新 **Qoder CN 编程智能体**,区别于传统辅助型编码插件,Qoder CN是面向软件开发全生命周期的**自主工程级AI智能体**,实现从单行代码补全、单文件编辑,升级为需求拆解、多文件批量修改、架构梳理、自动测试、部署调试的全流程自主开发能力,是目
1289 0
|
机器学习/深度学习 人工智能 计算机视觉
让AI真正"看懂"世界:多模态表征空间构建秘籍
本文深入解析多模态学习的两大核心难题:多模态对齐与多模态融合,探讨如何让AI理解并关联图像、文字、声音等异构数据,实现类似人类的综合认知能力。
4568 6
|
人工智能 关系型数据库 BI
算术逻辑单元ALU
算术逻辑单元ALU
4345 0
|
机器学习/深度学习 人工智能 并行计算
YOLOv11改进策略【YOLO和Mamba】| MLLA:Mamba-Like Linear Attention,融合Mamba设计优势的注意力机制
YOLOv11改进策略【YOLO和Mamba】| MLLA:Mamba-Like Linear Attention,融合Mamba设计优势的注意力机制
1109 9
一文教你学会keil软件仿真
一文教你学会keil软件仿真
3333 1
|
存储
原码,补码的乘法运算
原码,补码的乘法运算
1310 0
|
存储 算法 索引
【头歌·计组·自己动手画CPU】三、存储系统设计(HUST)(理论版) 【计算机硬件系统设计】
【头歌·计组·自己动手画CPU】三、存储系统设计(HUST)(理论版) 【计算机硬件系统设计】
3354 1