C/C++面试题—序列化二叉树

﹏ヽ暗。殇╰゛Y 2022-05-23 13:40 96阅读 0赞

# 题目描述 #

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

# 题目思路 #

在剑指offer中是采用的流的形式进行编写，这里将二叉树序列化为字符串，反序列化的时候将字符串反序列化为二叉树。序列化的时候用了 C++中现成的string数据结构，就不用担心空间容量的问题了。

# 题目代码 #

#include <iostream>
    #include <string>
    #include <fstream>
    #include <vector>
    #include <queue>
    #include "TreeNode.h"
    using namespace std;
    /* 题目描述 请实现2个函数，分别用来序列化和反序列化二叉树。 */
    class SolutionSerialize
    {
    public:
        char* Serialize(TreeNode *root) {
            if (root == nullptr)
                return nullptr;
            string *result = new string();
            SerializeCore(root, *result);
            return (char*)(*result).data();
        }
        void SerializeCore(TreeNode *root, string &result) {
            if (root == nullptr)
                result.append("$,");
            else
            {
                result.append(to_string(root->val).data()).append(",");
                SerializeCore(root->left, result);
                SerializeCore(root->right, result);
            }
        }
        TreeNode* Deserialize(char *str) {
            if (str == nullptr)
                return nullptr;
            TreeNode* root = nullptr;
            DeserializeCore(&str, &root);
            return root;
        }
        void DeserializeCore(char** str,TreeNode** root)
        {
            char* begin = *str;
            char* sperator = strchr(begin, ',');
            if (sperator == nullptr)
                return;
    
            int len = sperator - begin;
            char val[20] = { 0 };
            strncpy(val, begin, len);
            *str = sperator + 1;//str指针往后移动
    
            if (val[0] == '$')
                *root = nullptr;
            else
            {
                *root = new TreeNode(atoi(val));
                DeserializeCore(str, &(*root)->left);
                DeserializeCore(str, &(*root)->right);
            }
        }
    
        //分行打印
        void PrintFromTopToBottom2(TreeNode* root) {
            //vector<int> result;
            if (root == nullptr)
                return;// result;
            queue<TreeNode*> data;
            data.push(root);
            int toBePrinted = 1;
            int nextLevel = 0;
            while (!data.empty())
            {
                TreeNode* node = data.front();
                data.pop();
                toBePrinted--;
                //result.push_back(node->val);
                cout << node->val << " ";
                if (node->left != nullptr)
                {
                    data.push(node->left);
                    nextLevel++;
                }
                if (node->right != nullptr)
                {
                    data.push(node->right);
                    nextLevel++;
                }
                if (toBePrinted == 0)
                {
                    toBePrinted = nextLevel;
                    nextLevel = 0;
                    cout << endl;
                }
            }
            return;// result;
        }
    };
    
    int main(int argc, char *argv[])
    {
        /* 5 2 8 1 3 6 9 */
    
        SolutionSerialize solution;
        TreeNode t1(5);
        TreeNode t2(2); t1.left = &t2;
        TreeNode t3(8); t1.right = &t3;
        TreeNode t4(1); t2.left = &t4;
        TreeNode t5(3); t2.right = &t5;
        TreeNode t6(6); t3.left = &t6;
        TreeNode t7(9); t3.right = &t7;
        char* result = solution.Serialize(&t1);
        cout << result << endl;
        TreeNode *pRoot = solution.Deserialize(result);
        solution.PrintFromTopToBottom2(pRoot);
        return 0;
    }

# 测试验证 #

![这里写图片描述][70]

[70]: /images/20220523/cc4674ab110b46da9d3e5fac66ba3dcc.png