剑指 Offer 37. 序列化二叉树

题目

题解思路

1>源代码

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return []
        queue = []
        data = []
        queue.append(root)
        while queue:
            temp_node = queue.pop(0)
            if temp_node==None:
                data.append(null)
                continue
            data.append(temp_node.val)
            queue.append(temp_node.left)
            queue.append(temp_node.right)
        return data
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if len(data) == 0:
            return None
        root = TreeNode(data[0])
        queue = [root]
        index = 1
        while queue:
            temp_node = queue.pop(0)
            if data[index]!=null:
                temp_node.left = TreeNode(int(data[index]))
                queue.append(temp_node.left)
            index += 1
            if data[index]!=null:
                temp_node.right = TreeNode(int(data[index]))
                queue.append(temp_node.right)
            index += 1
        return root


# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

2>算法介绍

本题虽然是一道困难难度的题，但其实在算法课和数据结构课上很早就接触过，无非是层次遍历的实现和二叉树的反序列化，这两个步骤都需要借助队列来完成。

层次遍历的实现已经遇到过很多次了，在这里就不赘述，这里我们重点考虑一下反序列化的过程。

在遍历data数组时，我们维护一个队列。由于层次遍历是依照先左子树后右子树的顺序，所以我们在构造树的时候也采取如上顺序。这里需要注意的是如果遍历到’null’元素时，我们应不采取任何操作并将data数组的index加一，理由是每一个节点的左右孩子指针在初始化时就已经是None了，而且None也不存在左右孩子，也就意味着本次"子构造"到此为止了，树的深度不会继续增加。