剑指 Offer 37. 序列化二叉树（前序遍历，后序遍历，层次遍历）

2024-04-03 17:50:04

2021年02月12日周五天气晴【不悲叹过去，不荒废现在，不惧怕未来】

本文目录

1. 问题简介

剑指 Offer 37. 序列化二叉树

2. 题解

2.1 前序遍历（或后序遍历）

前序遍历在反序列化时应用递归比较简单，后序遍历在反序列化时，可以从后往前遍历，顺序就变成了 “根—>右—>左”，代码上和前序遍历只是略有区别。

而中序遍历得到的二叉树不唯一，不能保证反序列化的二叉树为原来的树，如下图所示。

图源 TIM_Y ，侵删。

前序遍历的代码如下：

/**
 * 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:
    // 序列化递归函数（前序遍历）
    void dfs(TreeNode* root, string& s){
        if(root==nullptr) s.append("#,");
        else{
            s.append(to_string(root->val));
            s.append(",");
            dfs(root->left, s);
            dfs(root->right, s);
        }
    }

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string s;
        dfs(root,s);
        return s;
    }

    // 反序列化递归函数（前序遍历）
    void dese(vector<string> &node, int& i, TreeNode* &root){
        if(i<node.size()){
            if(node[i]=="#"){
                ++i;
                root = nullptr;
                return;
            }
            root = new TreeNode(stoi(node[i]));
            ++i;
            dese(node,i,root->left);
            dese(node,i,root->right);
        }
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        // 手动实现split字符串分割函数 
        vector<string> node;
        stringstream ss(data);
        string word;
        while(getline(ss,word,','))
            node.emplace_back(word);

        TreeNode* root = nullptr;
        int i = 0;
        dese(node, i, root);
        return root;
    }
};

2.2 层序遍历

层序遍历，反序列化是重点：先判断树为空的情况，然后将根结点入队，安置好根结点的左右孩子，根据左右孩子是否为空来决定是否进入队列，进入队列的孩子结点再重复根结点经历的过程（加粗的地方）。

/**
 * 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) {
        string s;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            TreeNode* tmp = que.front();
            que.pop();
            if(tmp==nullptr) s.append("#,");
            else{
                s.append(to_string(tmp->val));
                s.append(",");
                que.push(tmp->left);
                que.push(tmp->right);
            }
        }
        return s;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.empty() || data[0]=='#') return nullptr;
        stringstream ss(data);
        vector<string> node;
        string word;
        while(getline(ss, word, ','))
            node.emplace_back(word);

        TreeNode* root = new TreeNode(stoi(node[0]));
        queue<TreeNode*> que;
        que.push(root);
        int i = 1;
        // 反序列化是重点
        while(!que.empty()){
            TreeNode* tmp = que.front();
            que.pop();
            // 安置左孩子
            if(node[i]!="#"){
                tmp->left = new TreeNode(stoi(node[i]));
                que.push(tmp->left);
            }
            ++i;
            // 安置右孩子
            if(node[i]!="#"){
                tmp->right = new TreeNode(stoi(node[i]));
                que.push(tmp->right);
            }
            ++i;
        }
        return root;
    }
};

参考文献

《剑指offer 第二版》

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-/

https://www.nowcoder.com/discuss/436465?type=0&order=0&pos=25&page=0&channel=-2&source_id=discuss_center_0

码农公寓