题解 | #序列化二叉树#

题目：https://www.nowcoder.com/practice/cf7e25aa97c04cc1a68c8f040e71fb84

ps：只有要遍历多一层空子节点，序列化二叉树的结果就会唯一。比如在前序遍历下表示为：1,2,3,4,#,#,5,#,#,#,#,对应唯一二叉树；但是1,2,3,4,5,不是对应唯一二叉树。

采用前序遍历来序列化二叉树，相比层次遍历有一点好处，虽然说层次遍历遍历起来更直观，但是需要存储更多的空子节点。举例

层次遍历表示下的二叉树：1,2,#,3,#,#,#,4,5,#,#,#,#,#,#,

在前序遍历下表示为：1,2,3,4,#,#,5,#,#,#,#,

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def __init__(self):
        self.s=''
        self.index=-1
    def inorder(self, root):#递归函数
        if not root:#递归到没有左右子节点的那种要加"#"表示空子节点
            self.s=self.s + '#,'
            return None
        self.s=self.s+str(root.val)+","
        self.inorder(root.left)
        self.inorder(root.right)            
            
    def Serialize(self, root):#调用递归函数
        if not root:
            self.s='#,'
            return self.s
        self.inorder(root)
        return self.s
                 
    def DeserializeFunction(self, arr):#arr是一个字符数组
        self.index=self.index+1#s[self.index]=='#'时，index要+1；s[self.index]!='#'时，index也要+1              
        if self.index>len(arr) or arr[self.index]=='#':
            return None#如果item是#，不需要构造它的子节点，直接结束。如果self.index>len(s)也直接结束
        node=TreeNode(int(arr[self.index]))
        node.left=self.DeserializeFunction(arr)
        node.right=self.DeserializeFunction(arr)
        return node
        
    def Deserialize(self, s):##调用递归函数        
        if s=='#,':#空树，返回None
            return None
        arr=s.split(",")  
        res=self.DeserializeFunction(arr)
        return res
    
    #关于递归中的return/return None。终止此次内部递归，开始下一轮的递归