首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

返回二叉树中从根到节点的路径

,可以使用深度优先搜索(DFS)算法来实现。DFS是一种递归的算法,通过遍历二叉树的每个节点,将路径上的节点值保存起来,直到遍历到叶子节点为止。

以下是一个示例的实现代码:

代码语言:txt
复制
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def binaryTreePaths(root):
    if not root:
        return []
    
    paths = []
    dfs(root, "", paths)
    return paths

def dfs(node, path, paths):
    if not node.left and not node.right:
        paths.append(path + str(node.val))
        return
    
    if node.left:
        dfs(node.left, path + str(node.val) + "->", paths)
    
    if node.right:
        dfs(node.right, path + str(node.val) + "->", paths)

这段代码中,binaryTreePaths函数是入口函数,它首先判断根节点是否为空,如果为空则直接返回空列表。然后创建一个空列表paths用于保存路径结果。接下来调用dfs函数进行深度优先搜索。

dfs函数接收三个参数:当前节点node、当前路径path和路径结果列表paths。首先判断当前节点是否为叶子节点,如果是,则将当前路径加上叶子节点的值添加到路径结果列表中。然后递归调用dfs函数遍历左子树和右子树,将当前路径加上当前节点的值和"->"符号传递给下一层递归。

最后,返回路径结果列表paths即可。

这个算法的时间复杂度是O(N),其中N是二叉树中的节点数。因为需要遍历每个节点一次。空间复杂度是O(N),其中N是二叉树中的节点数。因为需要保存每个节点的路径。

推荐的腾讯云相关产品是云服务器CVM(https://cloud.tencent.com/product/cvm)和云数据库MySQL(https://cloud.tencent.com/product/cdb_mysql)。云服务器CVM提供了弹性的计算资源,可以用于部署和运行应用程序。云数据库MySQL提供了高可用、可扩展的数据库服务,适用于存储和管理数据。

请注意,以上答案仅供参考,具体的产品选择和实现方式应根据实际需求和情况进行评估和决策。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

没有搜到相关的结果

领券