序列化二叉树

序列化二叉树_牛客题霸_牛客网

问题简述

请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。

思路1：DFS

• 有一道题是用 中序+前序/后序 还原二叉树；那道题使用单一的遍历无法还原二叉树——原因是没有记录空节点；

• 实际上如果保存了空节点，任意一种遍历方式都是可以还原二叉树的；

• 下面以前序遍历为例，后序、中序同理；

Python 写法1）使用索引指针

class Solution:
    def Serialize(self, root):
        
        def dfs(x, tmp):
            if not x: 
                tmp.append('#')
                return 
            
            tmp.append(str(x.val))
            dfs(x.left, tmp)
            dfs(x.right, tmp)
        
        ret = []
        dfs(root, ret)
        return ','.join(ret)
        
    def Deserialize(self, s):
        nodes = s.split(',')
        N = len(nodes)
        self.i = 0  # 全局索引指针
        
        def dfs(nodes):
            if self.i >= N or nodes[self.i] == '#':
                self.i += 1
                return None
            
            node = TreeNode(int(nodes[self.i]))
            self.i += 1
            node.left = dfs(nodes)
            node.right = dfs(nodes)
            return node
        
        return dfs(nodes)

Python 写法2）使用队列

class Solution:
    def Serialize(self, root):
        
        def dfs(x, tmp):
            if not x: 
                tmp.append('#')
                return 
            
            tmp.append(str(x.val))
            dfs(x.left, tmp)
            dfs(x.right, tmp)
        
        ret = []
        dfs(root, ret)
        return ','.join(ret)
        
    def Deserialize(self, s):
        from collections import deque
        nodes = deque(s.split(','))  # 这里使用队列来弹出头部节点
        
        def dfs(nodes):
            if not nodes or nodes[0] == '#':
                nodes.popleft()
                return None
            
            node = TreeNode(int(nodes.popleft()))
            node.left = dfs(nodes)
            node.right = dfs(nodes)
            return node
        
        return dfs(nodes)

思路2：BFS

• 使用层序遍历；

Python

class Solution:
    def Serialize(self, root):
        if not root: return ''
        
        from collections import deque
        q = deque([root])
        ret = []
        while q:
            p = q.popleft()
            if p:
                ret.append(str(p.val))
                q.append(p.left)
                q.append(p.right)
            else:
                ret.append('#')  # 添加空节点

        return ','.join(ret)
        
    def Deserialize(self, s):
        if not s: return None
        
        from collections import deque
        data = s.split(',')
        i = 0  # 索引指针
        root = TreeNode(int(data[i]))
        i += 1
        q = deque([root])
        
        while q:
            node = q.popleft()
            
            if data[i] != '#':
                node.left = TreeNode(int(data[i]))
                q.append(node.left)
            i += 1
            
            if data[i] != '#':
                node.right = TreeNode(int(data[i]))
                q.append(node.right)
            i += 1
            
        return root