二叉树序列化与反序列化

---

image.png image.png

一开始的想法是求先序+中序遍历字符串拼接在一起，然后再恢复，其实不必。

class Codec:
    def order(self, root):
        if root == None:
            return "#","#"
        preleft,inleft = self.order(root.left)
        preright,inright = self.order(root.right)
        return str(root.val)+","+preleft+","+preright,inleft+","+str(root.val)+","+inright
    def serialize(self, root):
        preorder,inorder=self.order(root)
        return preorder+"|"+inorder
    def check(self,data1,data2):
        d1={}
        d2={}
        for i in range(len(data1)):
            if data1[i] in d1:
                d1[data1[i]]+=1
            else:
                d1[data1[i]]=1
            
            if data2[i] in d2:
                d2[data2[i]]+=1
            else:
                d2[data2[i]]=1
        if sorted(list(d1.keys()))==sorted(list(d2.keys())):
            for i in d1.keys():
                if d1[i]!=d2[i]:
                    return False
            return True
        else:
            return False
    def decode(self,data1,l1,r1,data2,l2,r2):
        if l1>r1 or l2>r2:
            return None
        if data1[l1]=="#":
            return None
        if l1==r1 or l2==r2:
            return TreeNode(int(data1[l1]))
        for i in range(l2,r2+1):
            if data2[i]==data1[l1]:
                if self.check(data1[l1+1:i-l2+l1+1],data2[l2:i]):
                    break
        left=self.decode(data1,l1+1,l1+i-l2,data2,l2,i-1)
        right=self.decode(data1,l1+i-l2+1,r1,data2,i+1,r2)
        root=TreeNode(int(data1[l1]))
        root.left=left
        root.right=right
        return root

    def deserialize(self, data):
        data1,data2=data.split("|")
        data1=data1.split(",")
        data2=data2.split(",")
        return self.decode(data1,0,len(data1)-1,data2,0,len(data2)-1)

最优解：

对于 "#" 标记null的点可以只用前序遍历。中序没法知道root在哪里。后序也可以。

获取首节点start，输入start+1获取左子树的root节点和右子树的首节点位置前一位id。

class Codec:
    def order(self, root):
        if root == None:
            return "#"
        preleft = self.order(root.left)
        preright = self.order(root.right)
        return str(root.val)+","+preleft+","+preright
    def serialize(self, root):
        preorder=self.order(root)
        return preorder

    def decode(self,data,start):
        if data[start]=="#":
            return None,start
        if start>=len(data):
            return None,start
        left,id=self.decode(data,start+1)
        right,id=self.decode(data,id+1)
        node=TreeNode(data[start])
        node.left=left
        node.right=right
        return node,id
    def deserialize(self, data):
        data=data.split(",")
        node,id = self.decode(data,0)
        return node