二叉树的OJ输入反序列化，Python实现

二叉树的OJ输入反序列化，Python实现

• 1.配置环境
• 2.博客由来
• 3.问题描述
• 4.问题解决
• 5.结束语

1.配置环境

使用环境：python3.7
平台：Windows10
IDE：PyCharm

2.博客由来

博主在做笔试时遇到过关于二叉树的题目，题目中给定的二叉树输入是字符串输入，博主在数据转换上花费了不少功夫，特此记录

3.问题描述

将下列字符串表述的二叉树转化为链式储存的二叉树，其中字符串中元素为二叉树的层序排列，对于不存在的节点用None表示。

实例：

input:"[1,4,3,1,None,2,4,None,None,None,None,1,None,None,5]"

表示的二叉树为：

4.问题解决

老样子，先直接上代码：

# author:Hurricane
# date:  2022/4/5
# E-mail:hurri_cane@qq.com


from collections import deque


class Tree_node:
	def __init__(self, value):
		self.val = value
		self.left = None
		self.right = None


class Solution:
	def deserialize(self, data):
		if data == "[]":
			return None
		nums = data[1:-1].split(",")
		root = Tree_node(float(nums[0]))
		que = deque([root])
		i = 1
		while que and i < len(nums):
			node = que.popleft()
			if node:
				if nums[i] != "None":
					node.left = Tree_node(float(nums[i]))
				que.append(node.left)
				i += 1
				if nums[i] != "None":
					node.right = Tree_node(float(nums[i]))
				que.append(node.right)
				i += 1
			else:
				i += 2
				que.append(None)
				que.append(None)
		return root


if __name__ == '__main__':
	Solution_result = Solution()
	deserialize_result = Solution_result.deserialize("[1,4,3,1,None,2,4,None,None,None,None,1,None,None,5]")
	print("Deserialize Result:", deserialize_result)

思路：
通过指针（代码中为i）遍历序列化输入，采用一个队列来实现对子节点不断添加元素处理。

值得注意的是，由于空节点的子节点（也是空节点）在序列化输入上也占据了一个位置，即None，所以我们维护的队列中需要存储进去空节点，并且对空节点需要进行指针i后移两位的 *** 作。

5.结束语

如果本文对你有帮助的话还请点赞、收藏一键带走哦，你的支持是我最大的动力！(づ｡◕ᴗᴗ◕｡)づ