LeetCode算法题297--二叉树的序列化与反序列化

一、题目信息

• 原题链接

二、题目解读

• 我们需要制定出一套规则来完成二叉树的序列化与反序列化，序列化规则将二叉树的结点按某种顺序转化为字符串，反序列化规则将字符串恢复为二叉树。

• 这套规则对应的变换必须是双射的（一一对应的），即一棵二叉树只能与唯一一个字符串对应。

• 用字符#代表一个空结点（也是重要的一点）。

三、简单的分析

1.序列化

• 第二部分的第3点保证了空结点的可知，这样所有的结点都是可表示的。现在只要选取任何一种遍历方式就可以将一棵二叉树唯一地表示为一个字符串。

  

  2.反序列化

• 考虑一下为什么根据前中序或者后中序可以恢复二叉树？

  因为我们总可以根据前序或者后序找到根节点，然后在中序中确定根节点的左右子树，接着继续递归着构造下去。每个结点的父节点和孩子结点都是可确定的！

  

• 接下来就是找到可以轻松确定结点位置的规则，在序列化部分中我们可以使用4种遍历方式（前序、中序、后序和层次遍历），明显的层次遍历是我们的首选方式，原因（结合#的引入）是：

  $$对于编号为i (i=0,1,2, \cdots ) 的结点，它的左孩子编号为 2*i+1，它的右孩子编号为2*i+2 。$$

四、解题代码

1.C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        //空树
        if(root == NULL)
            return " #";
        string res;
        queue<TreeNode*> que;
        que.push(root);
        //层次遍历
        while(!que.empty()){
            TreeNode* node = que.front();
            que.pop();
            //节点存在
            if(node){
                res += " " + to_string(node->val);
                que.push(node->left);
                que.push(node->right);
            }
            else
                res += " #";
        }
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        //空树
        if(data == " #")
            return NULL;
        istringstream in(data);
        string str;
        in >> str;
        //队列
        queue<TreeNode*> que;
        //构造头节点
        TreeNode* res = new TreeNode(stoi(str));
        TreeNode* node = res;
        que.push(node);
        while(!que.empty()){
            TreeNode* now = que.front();
            que.pop();
            //str应该是now的子节点
            if(!(in >> str))
                break;
            if(str != "#"){
                node = new TreeNode(stoi(str));
                que.push(node);
                now->left = node;
            }
            if(!(in >> str))
                break;
            if(str != "#"){
                node = new TreeNode(stoi(str));
                que.push(node);
                now->right = node;
            }
        }
        return res;
    }
};

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

2.Python

# 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 root == None:
            return ' #'
        res, que = '', [root]
        #层次遍历
        while que != []:
            node = que.pop(0)
            if node:
                res += ' ' + str(node.val)
                que.append(node.left)
                que.append(node.right)
            else:
                res += ' #'
        return res

    def deserialize(self, data):
        """
        Decodes your encoded data to tree.
        :type data: str
        :rtype: TreeNode
        """
        #空树
        if data == ' #':
            return None
        #将data按' '进行切片
        strList = data.split()
        root = TreeNode(int(strList.pop(0))) #根节点
        que, val = [root], ''
        #层次遍历
        while que != []:
            cur = que.pop(0)
            val = strList.pop(0)
            if val != '#':
                node = TreeNode(int(val))
                que.append(node)
                cur.left = node
            val = strList.pop(0)
            if val != '#':
                node = TreeNode(int(val))
                que.append(node)
                cur.right = node
        return root

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

• 其他题目、其他语言的解题代码请移步我的GitHub存储库。