[数据结构与算法]二叉树序列化

通过字符串反序列化

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;

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

TreeNode* deserialize(string data) {
    if (!data.size()) return NULL;
    int i = 0, j = 0;
    vector<string> qs;
    queue<TreeNode*> que;
    while (i < data.size()) {
        if (data[i] != ',') i++;
        else {
            string str = data.substr(j, i - j);
            qs.push_back(str);
            i++;
            j = i;
        }
    }
    TreeNode* root = new TreeNode(stoi(qs[0]));
    que.push(root);
    i = 1;
    while (!que.empty()) {
        TreeNode* node = que.front();
        que.pop();
        if (qs[i] != "null") {
            node->left = new TreeNode(stoi(qs[i]));
            que.push(node->left);
        }
        i++;
        if (qs[i] != "null") {
            node->right = new TreeNode(stoi(qs[i]));
            que.push(node->right);
        }
        i++;
    }
    return root;
}

int res = 0;
int maxPath(TreeNode* root)
{
    if (!root->left && !root->right)
        return 0;
    int left = root->left ? maxPath(root->left) + 1 : 0;
    int right = root->right ? maxPath(root->right) + 1 : 0;
    res = max(res, left + right);
    return max(left, right);
}
int diameterOfBinaryTree(TreeNode* root)
{
    maxPath(root);
    return res;
}


int main() {
    string s = "1,2,3,4,5,null,null,null,null,null,null,";
    TreeNode* root = deserialize(s);
    cout << diameterOfBinaryTree(root) << endl;;
	return 0;
}

完整序列化逻辑：

/**
 * 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) {
       queue<TreeNode*> que;
       //if(!root) return "";
       if(root) que.push(root);
       string res;
       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+="null,";
       }
       cout<<"res: "<<res<<endl;
       return res; 
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(!data.size()) return NULL;
        int i=0,j=0;
        vector<string> qs;
        queue<TreeNode*> que;
        while(i<data.size()){
            if(data[i]!=',') i++;
            else{
                string str=data.substr(j,i-j);
                qs.push_back(str);
                i++;
                j=i;
            }
        }
        TreeNode* root=new TreeNode(stoi(qs[0]));
        que.push(root);
        i=1;
        while(!que.empty()){
            TreeNode* node=que.front();
            que.pop();
            if(qs[i]!="null"){
                node->left=new TreeNode(stoi(qs[i]));
                que.push(node->left);
            }
            i++;
            if(qs[i]!="null"){
                node->right=new TreeNode(stoi(qs[i]));
                que.push(node->right);
            }
            i++;
        }
        return root; 
    }
};

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