Go Java算法之二叉树的所有路径示例详解

目录
  • 二叉树的所有路径
  • 方法一：深度优先遍历搜索（Java）
  • 方法二：广度优先遍历（Go）

二叉树的所有路径

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

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

  • 示例 1：

输入：root = [1,2,3,null,5]

输出：["1->2->5","1->3"]

  • 示例 2：

输入：root = [1]

输出：["1"]

提示：

树中节点的数目在范围 [1, 100] 内

-100 <= Node.val <= 100

方法一：深度优先遍历搜索（Java）

最直观的方法是使用深度优先搜索。在深度优先搜索遍历二叉树时，我们需要考虑当前的节点以及它的孩子节点。

如果当前节点不是叶子节点，则在当前的路径末尾添加该节点，并继续递归遍历该节点的每一个孩子节点。

如果当前节点是叶子节点，则在当前路径末尾添加该节点后我们就得到了一条从根节点到叶子节点的路径，将该路径加入到答案即可。

递归二步曲：

(1) 找出重复的子问题。

  • 前序遍历的顺序是：根节点、左子树、右子树。
  • 在本题同样也是这个顺序：将根节点加入路径，递归左子树，递归右子树。
  • 对于左子树和右子树来说，也都是同样的操作。

(2) 确定终止条件。

对于二叉树的所有路径中的每条路径，当遍历到叶子节点的时候为当前路径的结束。并且将当前路径加入结果集。

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList<String>();
        constructPaths(root, "", paths);
        return paths;
    }
    public void constructPaths(TreeNode root, String path, List<String> paths) {
        if (root != null) {
            StringBuffer pathSB = new StringBuffer(path);
            pathSB.append(Integer.toString(root.val));
            if (root.left == null && root.right == null) {  // 当前节点是叶子节点
                paths.add(pathSB.toString());  // 把路径加入到答案中
            } else {
                pathSB.append("->");  // 当前节点不是叶子节点，继续递归遍历
                constructPaths(root.left, pathSB.toString(), paths);
                constructPaths(root.right, pathSB.toString(), paths);
            }
        }
    }
}

时间复杂度：O（N^2）

空间复杂度：O（N^2）

方法二：广度优先遍历（Go）

我们也可以用广度优先搜索来实现。

  • 我们维护一个队列，存储节点以及根到该节点的路径。一开始这个队列里只有根节点。
  • 在每一步迭代中，我们取出队列中的首节点
  • 如果它是叶子节点，则将它对应的路径加入到答案中。如果它不是叶子节点，则将它的所有孩子节点加入到队列的末尾。
  • 当队列为空时广度优先搜索结束
func binaryTreePaths(root *TreeNode) []string {
    paths := []string{}
    if root == nil {
        return paths
    }
    nodeQueue := []*TreeNode{}
    pathQueue := []string{}
    nodeQueue = append(nodeQueue, root)
    pathQueue = append(pathQueue, strconv.Itoa(root.Val))
    for i := 0; i < len(nodeQueue); i++ {
        node, path := nodeQueue[i], pathQueue[i]
        if node.Left == nil && node.Right == nil {
            paths = append(paths, path)
            continue
        }
        if node.Left != nil {
            nodeQueue = append(nodeQueue, node.Left)
            pathQueue = append(pathQueue, path + "->" + strconv.Itoa(node.Left.Val))
        }
        if node.Right != nil {
            nodeQueue = append(nodeQueue, node.Right)
            pathQueue = append(pathQueue, path + "->" + strconv.Itoa(node.Right.Val))
        }
    }
    return paths
}

时间复杂度：O（N^2）

空间复杂度：O（N^2）

以上就是Go Java算法之二叉树的所有路径示例详解的详细内容，更多关于Go Java算法二叉树所有路径的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • Go Java算法之交错字符串示例详解

    目录 交错字符串 方法一:动态规划(Java) 方法一:动态规划(GO) 交错字符串 给定三个字符串 s1.s2.s3,请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的. 两个字符串 s 和 t 交错 的定义与过程如下,其中每个字符串都会被分割成若干 非空 子字符串: s = s1 + s2 + ... + sn t = t1 + t2 + ... + tm |n - m| <= 1 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 +

  • Go Java算法之同构字符串示例详解

    目录 同构字符串 方法一:哈希表(Java) 方法一:哈希表(Go) 同构字符串 给定两个字符串 s 和 t ,判断它们是否是同构的. 如果 s 中的字符可以按某种映射关系替换得到 t ,那么这两个字符串是同构的. 每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序.不同字符不能映射到同一个字符上,相同字符只能映射到同一个字符上,字符可以映射到自己本身. 示例 1: 输入:s = "egg", t = "add" 输出:true 示例 2: 输入:s = &

  • Go和Java算法详析之分数到小数

    目录 分数到小数 方法一:模拟竖式计算(Java) 方法一:模拟竖式计算(Go) 总结 分数到小数 给定两个整数,分别表示分数的分子 numerator 和分母 denominator,以 字符串形式返回小数 . 如果小数部分为循环小数,则将循环的部分括在括号内. 如果存在多个答案,只需返回 任意一个 . 对于所有给定的输入,保证 答案字符串的长度小于 104 . 示例 1: 输入:numerator = 1, denominator = 2 输出:"0.5" 示例 2: 输入:num

  • Go Java算法之外观数列实现方法示例详解

    目录 外观数列 方法一:遍历生成(Java) 方法二:递归(Go) 外观数列 给定一个正整数 n ,输出外观数列的第 n 项. 「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述. 你可以将其视作是由递归公式定义的数字字符串序列: countAndSay(1) = "1" countAndSay(n) 是对 countAndSay(n-1) 的描述,然后转换成另一个数字字符串. 前五项如下: 1.1 —— 第一项是数字 1 2.11 —— 描述前一项,这个数

  • Go Java算法之比较版本号方法详解

    目录 比较版本号 方法一:字符串切割(Java) 方法二:双指针(Go) 比较版本号 给你两个版本号 version1 和 version2 ,请你比较它们. 版本号由一个或多个修订号组成,各修订号由一个 '.' 连接.每个修订号由 多位数字 组成,可能包含 前导零 .每个版本号至少包含一个字符. 修订号从左到右编号,下标从 0 开始,最左边的修订号下标为 0 ,下一个修订号下标为 1 ,以此类推.例如,2.5.33 和 0.1 都是有效的版本号. 比较版本号时,请按从左到右的顺序依次比较它们的

  • Go Java算法之从英文中重建数字示例详解

    目录 从英文中重建数字 Java实现 Go实现 从英文中重建数字 给你一个字符串 s ,其中包含字母顺序打乱的用英文单词表示的若干数字(0-9).按 升序 返回原始的数字. 示例 1: 输入:s = "owoztneoer" 输出:"012" 示例 2: 输入:s = "fviefuro" 输出:"45" 提示: 1 <= s.length <= 105 s[i] 为 ["e","g&

  • Go Java算法之二叉树的所有路径示例详解

    目录 二叉树的所有路径 方法一:深度优先遍历搜索(Java) 方法二:广度优先遍历(Go) 二叉树的所有路径 给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径. 叶子节点 是指没有子节点的节点. 示例 1: 输入:root = [1,2,3,null,5] 输出:["1->2->5","1->3"] 示例 2: 输入:root = [1] 输出:["1"] 提示: 树中节点的数目在范围 [1,

  • Go Java算法之Excel表列名称示例详解

    目录 Excel表列名称 方法一:数学(Java) 方法一:数学(Go) Excel表列名称 给你一个整数 columnNumber ,返回它在 Excel 表中相对应的列名称. 例如: A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ... 示例 1: 输入:columnNumber = 1 输出:"A" 示例 2: 输入:columnNumber = 28 输出:"AB"

  • java算法之二分查找法的实例详解

    java算法之二分查找法的实例详解 原理 假定查找范围为一个有序数组(如升序排列),要从中查找某一元素,如果该元素在此数组中,则返回其索引,否则返回-1.通过数组长度可取出中间位置元素的索引,将其值与目标值比较,如果中间位置元素值大于目标值,则在左部分进行查找,如果中间位置值小于目标值,则在右部分进行查找,如此循环,直到结束.二分查找算法之所以快是因为它没有遍历数组的每个元素,而仅仅是查找部分元素就能找到目标或确定其不存在,当然前提是查找范围为有序数组. Java的简单实现 package me

  • Java设计模式之责任链模式的示例详解

    目录 应用场景 实际代码案例 无模式情况下的代码 采用责任链模式优化代码 采用建造者+责任链模式优化代码 责任链模式优缺点 责任链模式是将链中的每一个节点看做是一个对象,每个节点处理的请求均不相同,且内部自动维护下一个节点对象,当一个请求从链式的首段发出时,会沿着链的路径依次传递给每一个节点对象,直至有对象处理这个请求位置,属于行为模式. 这里需要注意的是每个节点都能对对象进行一定的处理(也可以不处理),处理完成之后节点再进行判断还要进行后续处理还是说传递给下一个节点. 应用场景 首先举一个日常

  • Java实战之实现物流配送系统示例详解

    Java实战之实现物流配送系统示例详解

    目录 介绍 效果图展示 主要实现代码 介绍 系统分普通用户.企业.超级管理员等角色,除基础脚手架外,实现的功能有: 超级管理员:系统管理.用户管理.企业用户管理.普通用户管理.货物类型管理.车辆管理.公告管理.使用帮助等. 普通用户:注册登录.个人信息管理(个人资料.密码修改.充值.订单管理等).货物浏览.公告查看.下单等. 企业用户:注册登录.修改密码.充值.订单管理.货物管理.车辆管理.安排车辆等. 运行环境:windows/Linux均可.jdk1.8.mysql5.7.redis3.0.

  • Java框架设计灵魂之反射的示例详解

    目录 获取Class对象的方式 Class对象功能 获取成员变量们 获取构造方法们 获取成员方法们 获取全类名 Field:成员变量 Constructor:构造方法 Method:方法对象 案例 框架:半成品软件.可以在框架的基础上进行软件开发,简化编码. 反射就是把Java类中的各个成员映射成一个个的Java对象. 即在运行状态中,对于任意一个类,都能够知道这个类的所有属性和方法: 对于任意一个对象,都能调用它的任意一个方法和属性. 这种动态获取信息及动态调用对象方法的功能叫Java的反射机

  • java开发ShardingSphere的路由引擎类型示例详解

    目录 ShardingSphere的路由引擎类型 路由引擎类型 标准路由 路由逻辑 总结 ShardingSphere的路由引擎类型 本篇文章源码基于4.0.1版本 上篇文章我们了解到了ShardingSphere在路由流程过程中,根据不同类型的SQL会现在不同的路由引擎,而ShardingSphere支持的路由规则也很多了,包括广播(broadcast)路由.混合(complex)路由.默认数据库(defaultdb)路由.无效(ignore)路由.标准(standard)路由以及单播(uni

  • Java结构型设计模式中代理模式示例详解

    目录 代理模式 分类 主要角色 作用 静态代理与动态代理的区别 静态代理的基本使用 创建抽象主题 创建真实主题 创建代理主题 客户端调用 JDK动态代理的基本使用 创建抽象主题 创建真实主题 创建代理主题 客户端调用 小优化 CGLIB动态代理的基本使用 创建抽象主题 创建真实主题 创建代理主题 客户端调用 小优化 CGLIB与JDK动态代理区别 1.执行条件 2.实现机制 3.性能 代理模式 代理模式(Proxy Pattern)属于结构型模式. 它是指为其他对象提供一种代理以控制对这个对象的

  • Java结构型设计模式中建造者模式示例详解

    Java结构型设计模式中建造者模式示例详解

    目录 建造者模式 概述 角色 优缺点 应用场景 基本使用 创建产品类 创建建造者类 使用 链式写法 创建产品类与建造者类 使用 建造者模式 概述 建造者模式(Builder Pattern)属于创建型模式. 它是将一个复杂的构建与其表示相分离,使得同样的构建过程可以创建不同的表示. 简而言之:建造者模式就是使用多个简单的对象一步一步构建成一个复杂的对象. 建造者模式适用于创建对象需要很多步骤,但是步骤的顺序不一定固定.如果一个对象有非常复杂的内部结构(很多属性),可以将复杂对象的创建和使用进行分

随机推荐