算法 dfs —— 将二叉树 先序遍历 转为 链表
2024-08-30 22:45:15
将二叉树拆成链表
中文English
将一棵二叉树按照前序遍历拆解成为一个 假链表。所谓的假链表是说，用二叉树的 right 指针，来表示链表中的 next 指针。
Example
样例 1：
输入：{1,2,5,3,4,#,6}
输出：{1,#,2,#,3,#,4,#,5,#,6}
解释：
1
/ \
2 5
/ \ \
3 4 6
1
\
2
\
3
\
4
\
5
\
6
样例 2：
输入：{1}
输出：{1}
解释：
1
1
Challenge
不使用额外的空间耗费。
Notice
不要忘记将左儿子标记为 null，否则你可能会得到空间溢出或是时间溢出。
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
""" class Solution:
"""
@param root: a TreeNode, the root of the binary tree
@return: nothing
"""
def flatten(self, root):
# write your code here
if not root:
return
last_node = dummy = TreeNode(None)
stack = [root]
while stack:
node = stack.pop()
last_node.right = node
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
node.left, node.right = None, None
last_node = node
class Solution:
last_node = None """
@param root: a TreeNode, the root of the binary tree
@return: nothing
"""
def flatten(self, root):
if root is None:
return if self.last_node is not None:
self.last_node.left = None
self.last_node.right = root self.last_node = root
right = root.right
self.flatten(root.left)
self.flatten(right)
后者是使用递归的解法。但是要注意变量修改的细节。
需要在遍历中记住上次遍历节点，根据上次的节点和当前节点进行比较而得到result的算法模板：
class Solution():
last_node = None
result = None def run(self, root):
self.dfs(root)
return self.result def dfs(self):
if last_node is None:
last_node = root
else:
do_sth(last_node, root) dfs(root.left) dfs(root.right)
最新文章
- BCP导出导入大容量数据实践
- Python 文件读写，条件循环（三次登录锁定账号实例）
- mysql 的2个关于事务和安全性的参数
- 用自己的算法实现startsWith和endsWith功能
- python_way ,day22 tonardo
- iOS产品开发流程
- Android Studio Check for Update
- 如何在ARC代码中混编非ARC代码
- web工程中URL地址的写法
- Android 发送HTTP GET POST 请求以及通过 MultipartEntityBuilder 上传文件
- EasyUI-datagrid获取编辑行的数据
- webpack入门篇--1.简单介绍
- netty的基本介绍
- k64 datasheet学习笔记22---Direct Memory Access Controller (eDMA)
- 潭州课堂25班：Ph201805201 爬虫高级 第十二 课 Scrapy-redis分布 项目实战 (课堂笔记)
- Mybatis返回值类型是hashmap，输入键值对为空时，key 丢失的问题
- [VS工具]如何让#region...#endregion在ashx文件页面上折叠
- Adroid我还是个菜鸟——导入jar包
- /var/log/messages Logging not working on Centos 7
- VMware Coding Challenge: Possible Scores && Summary: static