Lever's Castle
297. 二叉树的序列化与反序列化
January 08, 2019
https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
使用语言：Python/JavaScript
看了一遍题目之后，想到的最简单的办法就是 JSON.stringify()/JSON.parse()，这对 js 来讲简直就是小菜一碟。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* Encodes a tree to a single string.
*
* @param {TreeNode} root
* @return {string}
*/
var serialize = function(root) {
return JSON.stringify(root)
};
/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function(data) {
return JSON.parse(data)
};
/**
* Your functions will be called as such:
* deserialize(serialize(root));
*/但是本着对自我高要求的心态，这道题还是要想别的方式好好做一下的。
首先想把一颗树用字符串的形式表达出来，自然想到了那几种遍历树的方式 —— 前序遍历、中序遍历、后序遍历、广度优先遍历等，在之前写的 恢复二叉搜索树 中也具体讲过，这里就不加赘述了。
下面我用前序遍历的方式对树进行了 serialize，要从字符串重新构造树，也要用同样的遍历方式。
在序列化时，要注意我们把叶子节点的左右孩子都当成空也加入到了结果字符串中，这是为了反序列化时，能够明确每个节点的位置，可以理解为是用来占位的。如果不加入这个占位信息，那么你是没办法只用一种遍历方式就能明确节点的位置的，至少需要两种遍历方式关联起来来确定其位置 (比如：前序遍历 + 中序遍历)。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
def serializeHelper(root, s):
if not root:
s += ","
else:
s += str(root.val) + ","
s = serializeHelper(root.left, s)
s = serializeHelper(root.right, s)
return s
return serializeHelper(root, "")
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
index = 0
nodes = data.split(",")
def deserializeHelper():
nonlocal index
if index >= len(nodes) or not nodes[index]:
index += 1
return None
treeNode = TreeNode(int(nodes[index]))
index += 1
if treeNode:
treeNode.left = deserializeHelper()
treeNode.right = deserializeHelper()
return treeNode
return deserializeHelper()
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))
痕迹
没有过去，就没法认定现在的自己