思路

题目分析

1. 题目给出我们一棵树，要求我们实现两个函数
2. 第一个函数要求我们以任意遍历方式返回一个字符串
3. 第二个函数要求我们可以从上一个字符串中重新返回这棵树

• 方法一：递归

  • 我们采用前序遍历的方式构造字符串并恢复树
  • 序列化过程
    • 递归函数退出条件是当节点为空，则返回"#"。我们一定要用一个"#"来实现占位的操作，这样才能保证我们的树是唯一的，否则单独前序遍历出来的字符串是无法恢复成唯一的一棵树的
    • 然后我们递归地返回 当前值+","+递归左子节点+","+递归右子节点
  • 反序列化过程
    • 我们引入了一个新的结构queue来储存字符串分割后的前序遍历结果
    • 由于前序遍历，我们首先从queue中取出队首，将其对象化成为一个节点
    • 然后将左子节点值设为递归这个queue的函数返回结果
    • 然后将右子节点值设为递归这个queue的函数返回结果
    • 这正好符合了前序遍历的规则，我们倒着又建立了这棵树

• 方法二：迭代

  • 我们采用层序遍历的方式迭代
  • 序列化过程
    • 队列中存储一层的节点信息
    • 遍历该层的时候进行对字符串的构造
    • 同时不断地压入下一层的节点信息
    • 最终给返回字符串
  • 反序列化过程
    • 引入一个aux队列来辅助建立树
    • aux队列首先同样拿到一层的节点信息
    • 然后配合队列q的信息进行父子节点对应弹出的操作，也就是说aux弹出一次，q中相应的弹出其对应的父子节点
    • 最终返回建立好的树

方法一：递归

class Solution:
    def Serialize(self, root):
        # write code here
        if root == None:
            return "#"
        return str(root.val) +","+self.Serialize(root.left) +","+ self.Serialize(root.right)
    def Deserialize(self, s):
        # write code here
        s = s.split(",")
        queue = []
        while s:
            queue.append(s.pop(0))
        return self.de(queue)
    def de(self, queue):
        s = queue.pop(0)
        if s == "#":
            return None
        node = TreeNode(int(s))
        node.left = self.de(queue)
        node.right = self.de(queue)
        return node