剑指offer刷题笔记61（python）

题目描述

请实现两个函数，分别用来序列化和反序列化二叉树。

思路

一、 二叉树的序列化 二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字 符串，从而使得内存中建立起来的二叉树可以持久保存。 序列化可以基于先序、中序、后序、层次遍历的二叉树遍历方式来进行序列化。原理都是一样的（即遍历顺序不同而已，对每个结点的处理都是一样的），序列化的结果是一个字符串，序列化时通过某种符号表示空节点（#）。 这里以先序遍历的方式对二叉树进行序列化。

先序序列化二叉树：定义一个res数组保存序列过程中的结果：按照先序遍历方式遍历二叉树，若结点非空则把 “结点值” append到res中；若结点空则把 “#” append到res中；最后用用res数组生成字符串就是序列化结果。

二、 二叉树的反序列化 二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

先序序列化结果重构二叉树：分割二叉树的序列化字符串，遍历nodes数组建立二叉树，如果当前遍历元素非 # 则作为一个结点插入树中作为上一结点的左儿子，当前遍历元素为 # 则表示此子树已结束，遍历下一元素作为上一结点的右儿子。

代码

# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def Serialize(self, root): # write code here vallist = [] def preOrder(root): if not root: vallist.append('#') else: vallist.append(str(root.val)) preOrder(root.left) preOrder(root.right) preOrder(root) return ' '.join(vallist) def Deserialize(self, s): # write code here vallist = iter(s.split()) # 利用分隔好的字符串生成的数组生成一个迭代器。可以不断被next调用，每调用一次他就会返回下一个元素。 def dePre(): val = next(vallist) # 通过next不断调用vallist这个迭代器里的元素，相当于for循环。 if val == "#": return None node = TreeNode(int(val)) node.left = dePre() node.right = dePre() return node return dePre()

上面使用了一个迭代器，通过next不断调用迭代器里的元素。这里也可以利用一个队列，不断返回队列中最左边的元素，并删除。