剑指offer 序列化二叉树

Posted on |

序列化二叉树

题目

请实现两个函数，分别用来序列化和反序列化二叉树

方法

方法1：深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Serialize(self, root):
        # write code here
        res=[]

        def preorder(node):
            if not node:
                res.append('#')
            else:
                res.append(str(node.val))
                preorder(node.left)
                preorder(node.right)
        preorder(root)
        return ','.join(res)

    def Deserialize(self, s):
        # write code here
        data=s.split(',')
        def func(data):
            val=data.pop(0)
            if val=='#':
                return None
            else:
                node=TreeNode(int(val))
                node.left=func(data)
                node.right=func(data)
                return node
        return func(data)

方法2：宽度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Serialize(self, root):
        # write code here
        stack,res=[root],[]
        while stack:
            node=stack.pop(0)
            if not node:
                res.append('#')
            else:
                res.append(str(node.val))
                stack.append(node.left)
                stack.append(node.right)
        return ','.join(res)

    def Deserialize(self, s):
        # write code here
        data=s.split(',')
        if data[0]=='#':
            return None
        root=TreeNode(int(data[0]))
        stack=[root]
        i=0
        while stack:
            node=stack.pop(0)
            node.left=TreeNode(int(data[i+1])) if data[i+1]!='#' else None
            node.right=TreeNode(int(data[i+2])) if data[i+2]!='#' else None
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
            i+=2
        return root