2019-08-23 剑指 序列化二叉树

45min

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def Serialize(self, root:TreeNode):
        res=[]
        self.dfs_ser(root,res)
        res=map(lambda x:str(x),res)
        return ",".join(res)  # 字符串函数传递无法改变值，使用list真的妙哉

    def dfs_ser(self,root:TreeNode,res:List ):
        if not root:
            res.append("#")
            return
        res.append(root.val)
        self.dfs_ser(root.left,res)
        self.dfs_ser(root.right,res)

    def Deserialize(self, s:str):
        res=s.split(',')
        root=self.dfs_de(res)
        return root

    def dfs_de(self,res):
        if res[0]=='#':
            res.pop(0) # 找不到头绪时，用具体的例子在脑海里过一遍
            return None
        elif res[0].isdigit():
            root=TreeNode(int(res[0]))
            res.pop(0)
            root.left=self.dfs_de(res)
            root.right=self.dfs_de(res)
        return root


if __name__ == '__main__':
    t=Solution()
    # print(t.Deserialize("1,23,3,#"))
    root=TreeNode(1)
    a=TreeNode(2)
    b=TreeNode(3)
    root.left=a
    root.right=b
    s=t.Serialize(root)
    print(s)
    k=t.Deserialize(s)
    print(k.val)
    print(k.left.val)
    print(k.right.val)