程序员代码面试指南 3.4：二叉树的序列化和反序列化

1、思路

• 跟普通的二叉树先序遍历和层序遍历一样，只不过用string替代了vector。

• 注意建树方式。

2、代码

#include <iostream>
#include <string> 
#include <queue>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left, *right;
    TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}
};

void createTree(TreeNode* root, int& n)     //建树
{
    if (n == 0) return;

    int rootVal, leftVal, rightVal;
    cin >> rootVal >> leftVal >> rightVal;

    if (leftVal != 0)
    {
        root->left = new TreeNode(leftVal);
        createTree(root->left, -- n);
    }

    if (rightVal != 0)
    {
        root->right = new TreeNode(rightVal);
        createTree(root->right, -- n);
    }
}

string preOrderList(TreeNode* root)         //先序序列化（递归方式）
{
    if (root == nullptr) return "#!";

    string res = to_string(root->val) + "!";
    res += preOrderList(root->left);
    res += preOrderList(root->right);

    return res;
}

string levelOrderList(TreeNode* root)       //层序序列化
{
    if (root == nullptr) return "#!";

    string res = "";
    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty())
    {
        TreeNode* node = q.front();
        q.pop();

        if (node == nullptr)
        {
            res += "#!";
        }
        else
        {
            res += to_string(node->val) + "!";
            q.push(node->left);
            q.push(node->right);
        }
    }

    return res;
}

int main()
{
    int n, rootVal;
    cin >> n >> rootVal;
    TreeNode* root = new TreeNode(rootVal);

    createTree(root, n);
    string preOrderRes = preOrderList(root);
    string levelOrderRes = levelOrderList(root);

    cout << preOrderRes << endl << levelOrderRes;

    return 0;
}