本文共 4486 字，大约阅读时间需要 14 分钟。

这篇略长，大家耐心点

这个可视化好看些

【思路1】层次遍历（BFS）广度优先遍历

这里分两部分讲

1.序列化

序列化的字符串实际上是二叉树的 “层序遍历”（BFS 广度优先遍历）结果，参见

先上图

''' # 和 null 都行,都表示空,但要统一,要么全用'#',要么全用null。'''class Codec:	# 1.序列化    def serialize(self, root):        ans = ''        queue = [root]        while queue:            node = queue.pop(0)            if node:                ans += str(node.val) + ','                queue.append(node.left)                queue.append(node.right)            else:            	# 除了这里不一样，其他和普通的不记录层的 BFS 没区别                ans += '#,'        # print(ans[:-1])        return ans[:-1]		# 末尾会多一个逗号，我们去掉它。

注意：在 序列化函数 中 ans 是 str 类型，执行

ans += str(node.val) + ','

后，ans = 1,2,3,#,#,4,5,#,#,#,# 也是一个 str 类型的字符串，该字符串 长度为为 21 (逗号也是一个元素，这里跟 列表list 不一样)

.

.

而后在 反序列化函数 中，

nodes = data.split(',')	# 通过 ',' 分隔每个元素，可以得到 11 个节点的列表

通过 ‘,’ 分隔每个元素，得到 11 个节点的列表，所以 需要遍历【len(node)-2】次，即11次。

又因为 i+=2，所以遍历5次

2.反序列化

反序列化的理论基础：	给所有节点从左到右从上到下依次从 1 开始编号。	那么已知一个节点的编号是 i，	那么其左子节点就是 2 * i，	右子节点就是 2 * 1 + 1，	父节点就是 (i + 1) / 2。

# 2.反序列化    def deserialize(self, data):	    if data == '#': 	    	return None	    nodes = data.split(',')	# 通过 ',' 分隔每个元素，得到 11 个节点	    	    root = TreeNode(nodes[0])	    q = collections.deque([root])	    i = 0	    while q and i < len(nodes) - 2:	        cur = q.popleft()	        lv = nodes[i + 1]	        rv = nodes[i + 2]	        # print('cur =',cur.val,end='\t')	# 这里打印的是val值，其实它指向的是地址            # print('lv =',lv,end='\t')            # print('rv =',rv,end='\n')	        i += 2	        if lv != '#':	            l = TreeNode(lv)	            q.append(l)	            cur.left = l	        if rv != '#':	            r = TreeNode(rv)	            q.append(r)	            cur.right = r		    return root'''作者：fe-lucifer链接：https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/solution/297-er-cha-shu-de-xu-lie-hua-yu-fan-xu-lie-hua-12/来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。'''

有没有一点懵？

【思路2】

该方法的理论基础同思路1，不一样的之处如下：

• res为列表，每个节点(包括空)为一个元素
• 在序列化函数最后，再添加 逗号
• 反序列化用 split 分割的，还是得到一个列表（每个 str 类型的节点值），所以需要 int
• 循环中的 i 分两次 +
• 这点比较巧妙！不用指针，不用控制循环次数，queue结束就退出循环。

class Codec:    def serialize(self, root):        if not root: return "[]"        queue = collections.deque()        queue.append(root)        res = []        while queue:            node = queue.popleft()            if node:                res.append(str(node.val))                queue.append(node.left)                queue.append(node.right)            else:             	res.append("null")        return '[' + ','.join(res) + ']'    def deserialize(self, data):        if data == "[]": return        vals, i = data[1:-1].split(','), 1                root = TreeNode(int(vals[0]))        queue = collections.deque()        queue.append(root)        while queue:            node = queue.popleft()            if vals[i] != "null":                node.left = TreeNode(int(vals[i]))                queue.append(node.left)            i += 1            if vals[i] != "null":                node.right = TreeNode(int(vals[i]))                queue.append(node.right)            i += 1        return root'''作者：jyd链接：https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/solution/mian-shi-ti-37-xu-lie-hua-er-cha-shu-ceng-xu-bian-/来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。'''

【思路3】先序遍历（递归法）

话不多说，看图

• 序列化函数：采用 先序遍历（根 左 右） 的方式实现，字符串之间用 ‘,’ 隔开。
  
  注：ans 是 str 类型
• 反序列化函数：按先序遍历“根左右”的顺序，根节点位于其左右子节点的前面，即 非空（#） 的第一个节点是某子树的根节点，左右子节点在该根节点后，以 空节点# 为分隔符。
  

class Codec:	# 1.反序列函数	def serialize(self, root):        if not root:            return '#'        #print('这次root为=',root.val)        ans = str(root.val) + "," + self.serialize(root.left) + "," +self.serialize(root.right)        #print('返回ans=',ans)        #print('\n')        return ans        	# 2.反序列函数    def deserialize(self, data):        data_list = data.split(',')        print(data_list)        def decoder(data_list):            if len(data_list)<=0:                return None            data_val = data_list.pop(0)            print('data_val = ',data_val)            root = None            if data_val != '#':     # 为空(#)就跳过,非空就建立节点,                print('此时data_list还剩 = ',data_list)                print('\n')                root = TreeNode(int(data_val))                root.left = decoder(data_list)                root.right = decoder(data_list)                    return decoder(data_list)# 链接 https://blog.csdn.net/u010005281/article/details/79787278

显然，递归更快

~蟹蟹♪(･ω･)ﾉ支持 ~