【Leetcode刷题Python】114. 二叉树展开为链表

简介: LeetCode上114号问题"二叉树展开为链表"的Python实现,通过先序遍历二叉树并调整节点的左右指针,将二叉树转换为先序遍历顺序的单链表。

1 题目

给你二叉树的根结点 root ,请你将它展开为一个单链表:

展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1:

在这里插入图片描述

输入:root = [1,2,5,3,4,null,6]
输出:[1,null,2,null,3,null,4,null,5,null,6]

示例 2:

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

示例 3:

输入:root = [0]
输出:[0]

2 解析

在前序遍历结束之后更新每个节点的左右子节点的信息,将二叉树展开为单链表。

3 Python实现

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        preorder = []
        def dfs(node):
            if not node:
                return
            preorder.append(node)
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        for i in range(1,len(preorder)):
            prev,curr = preorder[i-1], preorder[i]
            prev.left = None
            prev.right = curr
目录
相关文章
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
342 1
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
387 0
Leetcode第21题(合并两个有序链表)
|
存储 Python
Python 实现单向链表,和单向链表的反转
链表是一种数据结构,每个节点存储相邻节点的位置信息。单链表中的节点仅存储下一节点的位置。通过Python实现单链表,定义`ListNode`类并关联节点可创建链表。例如,创建A->B->C的链表后,可通过反转函数`reverse`将链表反转为CBA。代码展示了如何实现和操作单链表。
498 6
Python 实现单向链表,和单向链表的反转
|
算法 Go
【LeetCode 热题100】23:合并 K 个升序链表(详细解析)(Go语言版)
本文详细解析了 LeetCode 热题 23——合并 K 个升序链表的两种解法:优先队列(最小堆)和分治合并。题目要求将多个已排序链表合并为一个升序链表。最小堆方法通过维护节点优先级快速选择最小值,;分治合并则采用归并思想两两合并链表。文章提供了 Go 语言实现代码,并对比分析两种方法的适用场景,帮助读者深入理解链表操作与算法设计。
635 10
|
存储 Python
Python 中链表的个人理解
简介:本文介绍了Python中链表的基本组成及其操作实现。链表由`head`(头节点)、中间节点和`tail`(尾节点)三部分构成,每个节点通过`Node`类定义,包含`value`(值域)和`next`(指针域)。示例代码展示了链表的增删查功能,包括`add`(头部插入)、`append`(尾部插入)、`remove`(删除节点)、`search`(查找节点)及遍历方法。运行结果验证了链表操作的正确性。
|
存储 算法 Python
文件管理系统中基于 Python 语言的二叉树查找算法探秘
在数字化时代,文件管理系统至关重要。本文探讨了二叉树查找算法在文件管理中的应用,并通过Python代码展示了其实现过程。二叉树是一种非线性数据结构,每个节点最多有两个子节点。通过文件名的字典序构建和查找二叉树,能高效地管理和检索文件。相较于顺序查找,二叉树查找每次比较可排除一半子树,极大提升了查找效率,尤其适用于海量文件管理。Python代码示例包括定义节点类、插入和查找函数,展示了如何快速定位目标文件。二叉树查找算法为文件管理系统的优化提供了有效途径。
398 5
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
存储 算法 搜索推荐
Python 实现反转、合并链表有啥用?
大家好,我是V哥。本文介绍Python实现反转链表和合并链表的应用场景及代码实现。反转链表适用于时间序列数据展示、回文链表判断等;合并链表则用于大规模数据排序、数据库查询结果集合并等。通过迭代和递归方法实现反转链表,以及合并两个或多个有序链表的算法,帮助开发者解决实际问题。关注V哥,了解更多实用编程技巧。 先赞再看后评论,腰缠万贯财进门。
453 0
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
608 1
|
搜索推荐 Python
Leecode 101刷题笔记之第五章:和你一起你轻松刷题(Python)
这篇文章是关于LeetCode第101章的刷题笔记,涵盖了多种排序算法的Python实现和两个中等难度的编程练习题的解法。
325 3

推荐镜像

更多