题解 | #序列化二叉树#

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/


#include <algorithm>
#include <cstdio>
#include <queue>

class Solution {
public:

    int count(TreeNode* root)
    {
        if(!root)
            return 0;
        int left=count(root->left);
        int right=count(root->right);
        return left+right+1;
    }

    char* Serialize(TreeNode *root) {    
        if(!root)
            return nullptr;
        TreeNode* p = root;
        int num  = count(p);
        char* ss = (char*)malloc(num*2);
        int i = 0; //用来记录当前遍历到哪个结点了
        int j=0;
        queue<TreeNode*> q;
        q.push(p);
        while(!q.empty())
        {
            p = q.front();
            q.pop();
            if(p)
            {
                ss[j++]= ((unsigned char)p->val);
                if(++i==num)
                    break;
                q.push(p->left);
                q.push(p->right);
            }            
            else {
                ss [j++]= '#';
            }
        }
        ss[j]='\0';
        return ss;
    }

    TreeNode* Deserialize(char *str) {
        if(!str && str[0]=='\0')
            return nullptr;
        TreeNode* head = new TreeNode((int)(unsigned char)str[0]);
        queue<TreeNode*> q;
        q.push(head);
        int num  =strlen(str);
        for(int i=0;i<num-1;i++)
        {
            TreeNode* p =q.front();
            q.pop();
            if(p)
            {
                if(2*i+1<num && str[2*i+1]!='#')
                {
                    TreeNode* left_node = new TreeNode((int)(unsigned char)str[2*i+1]);
                    p->left = left_node;
                    q.push(left_node);
                }
                if(2*i+2<num && str[2*i+2]!='#')
                {
                    TreeNode* right_node = new TreeNode((int)(unsigned char)str[2*i+2]);
                    p->right = right_node;
                    q.push(right_node);
                }
            }
        }
        return head;
    }
};

这个题可太复杂了，一环套一环。

这里我们选择层次序列。

首先要注意取值范围，题目中说了数据的大小为0-150，150已经超出了char的有效范围。并且注意值全部大于0，所以应该用到

unsigned char来保存。

A：转化为字符串

首先定义一个count函数用来计算该树有多少个非nullptr的结点数。

然后用i来控制访问到哪个结点，如果i==num,表示全部的结点已经遍历结束，则break

用j来控制字符串的位置，最后注意ss[i]='\0'

B:构造树

首先构造根节点，然后从i=0开始访问，依次构造第i个结点的孩子，最后遍历结束即可。