面试题37. 序列化二叉树（难）& LeetCode 297. 二叉树的序列化与反序列化（难）

序列化就是广度优先遍历，反序列化就是构造二叉树。

Question

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

示例：你可以将以下二叉树： 

1
2
3
4
5
  1
 / \
2   3
   / \
  4   5
序列化为 "[1,2,3,null,null,4,5]"

测试用例

功能测试（输入的二叉树是完全二叉树；所有节点都没有左/右子树的二叉树；只有一个节点的二叉树；所有节点的值都相同的二叉树）。 特殊输入测试（指向二叉树根节点的指针为 nullptr 指针）。

本题考点

考查应聘者分析复杂问题的能力。为了把这个问题分析清楚，我们可以把树分为3部分：根节点、左子树和右子树，在序列化/反序列化根节点之后再分别序列化/反序列化左、右子树，因此可以递归解决。解决这个问题的关键在于把一个大的问题分解成几个小问题，并递归地解决小问题。 考查应聘者对二叉树遍历的理解及编程能力。

Intuition

序列化就是广度优先遍历。 反序列化就是构造二叉树，可以基于队列构造，也可以基于前序遍历构造。

Code

  • 循环解法
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string. 广度优先遍历
        :type root: TreeNode
        :rtype: str
        """
        res = []
        if root == None:  return res
        queue = []
        queue.append(root)
        while len(queue):
            # 可以选择提前结束，不过由于调用了内建方法，会影响整体效率。
            # if set(queue) == set([None]):
            #     break
            node = queue.pop(0)
            if node:
                res += [str(node.val)]
                queue.append(node.left)
                queue.append(node.right)
            else:
                res += ["null"]
        
        return "[{}]".format(",".join(res))


    def deserialize(self, data):
        """Decodes your encoded data to tree. 利用字符串构建二叉树
        :type data: str
        :rtype: TreeNode
        """
        if data == "":  return None
        if data == []:  return None  # 你永远不知道，LeetCode的输入是什么。
        items = [int(x) if x !='null' else None for x in data[1:-1].split(',')]
        if len(items) == 0:  return None
        nodeQueue = []  # nodeQueue保存的是这一层所有非空节点，要留着给下一层创建左右子树的时候用。
        root = TreeNode(items[0])  # 创建一个根节点
        nodeQueue.append(root)  # 将根节点加入队列
        cur = None
        lineNodeNum = 1*2  # 记录下一层需要填充的节点的数量（注意不一定是2的幂，而是上一行中非空节点的数量乘2），第二层的节点数肯定是1*2。
        startIndex = 1  # 记录当前行中数字在数组中的开始位置，第0个位置在根节点，则第第二行第一个位置肯定是items[1]。
        restLength = len(items) - 1  # 记录数组中除去根节点剩余的元素的数量。
        while restLength > 0:  # 只要还有剩，就要继续添加。  
            i = startIndex
            while i < startIndex + lineNodeNum:  # 一次while循环会处理掉一个layer。
                if i == len(items):  return root  # 说明已经将nums中的数字用完，此时应停止遍历，并可以直接返回root
                cur = nodeQueue.pop(0)  # cur是上一行的根节点。
                if items[i] != None:  # 如果是None，就不做处理，保留左节点为None的情况。
                    cur.left = TreeNode(items[i])
                    nodeQueue.append(cur.left)

                if i + 1 == len(items):  return root  # 同上，做一个边界判定。
                if items[i + 1] != None:  # 同上，如果是None，就不做处理，保留右节点为None的情况。
                    cur.right = TreeNode(items[i + 1])
                    nodeQueue.append(cur.right)
                i += 2
            startIndex += lineNodeNum  # 加上这一层已经处理掉的数字，就是下一层要处理的数字的起点。
            restLength -= lineNodeNum  # 减去这一层已经处理掉的数字，就是剩余还未处理的数字的个数。
            lineNodeNum = len(nodeQueue) * 2  # nodeQueue的长度就是这一层的非空节点的个数，乘以2就是下一层需要填充的节点的数量。
        return root
  • 一种简洁的循环解法
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
class Codec:
    def serialize(self, root):
        if not root: return "[]"
        queue = collections.deque()
        queue.append(root)
        res = []
        while queue:
            node = queue.popleft()
            if node:
                res.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else: res.append("null")
        return '[' + ','.join(res) + ']'

    def deserialize(self, data):
        if data == "[]": return
        vals, i = data[1:-1].split(','), 1
        root = TreeNode(int(vals[0]))
        queue = collections.deque()
        queue.append(root)
        while queue:
            node = queue.popleft()
            if vals[i] != "null":
                node.left = TreeNode(int(vals[i]))
                queue.append(node.left)
            i += 1
            if vals[i] != "null":
                node.right = TreeNode(int(vals[i]))
                queue.append(node.right)
            i += 1
        return root

参考链接

作者：jyd 链接：https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/solution/mian-shi-ti-37-xu-lie-hua-er-cha-shu-ceng-xu-bian-/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

  • 递归解法
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
39
class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return []
        result = []
        def encodes(root):
            if not root:
                result.append('$')
                return
            result.append(root.val)
            encodes(root.left)
            encodes(root.right)
        encodes(root)
        return result

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        :type data: str
        :rtype: TreeNode
        """
        if not data:
            return []
        index = [0] #全局变量
        def decodes(data):
            if data[index[0]] == '$':
                index[0] += 1
                return None
            node = TreeNode(data[index[0]])
            index[0] += 1
            node.left = decodes(data)
            node.right = decodes(data)
            return node
    
        return decodes(data)

参考链接

作者：xiao-xue-66 链接：https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/solution/pythonti-jie-qian-xu-bian-li-jie-fa-jian-dan-yi-do/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。