序列化二叉树

http://www.nowcoder.com/questionTerminal/cf7e25aa97c04cc1a68c8f040e71fb84

#描述这是一篇针对初学者的题解，共用两种方法解决。知识点：二叉树，先序遍历，层次遍历难度：二星

#题解题目描述：给定一颗二叉树，将其序列化和反序列化。

##方法一：先序遍历实现预备知识：先序遍历的递归实现：

void pre_order(TreeNode *root) {
	if (!root) {
		return;
	}

	// process root
	// ...
	pre_order(root-&gt;left);
	pre_order(root-&gt;right);
}

对于本题来说，可以套用上述模板。假设序列化的结果为字符串 str, 初始str = "".根据要求，遇到nullptr节点，str += "#" 遇到非空节点，str += "val" + "!"; 假设val为3，就是 str += "3!"

所以，序列化二叉树的代码为：

char* Serialize(TreeNode *root) {    
    if (!root) {
        return "#";
    }

    string res = to_string(root-&gt;val);
    res.push_back(',');

    char* left = Serialize(root-&gt;left);
    char* right = Serialize(root-&gt;right);

    char* ret = new char[strlen(left)+strlen(right)+res.size()];
    // 如果是string类型，直接用operator += ,这里char* 需要用函数
    strcpy(ret,res.c_str());
    strcat(ret,left);
    strcat(ret,right);

    return ret;
}

反序列化的结果，就是根据先序遍历，再重建二叉树即可。代码如下：

// 参数使用引用&amp;， 以实现全局变量的目的
TreeNode* deseri(char *&amp;s) {
	if (*s == '#') {
		++s;
		return nullptr;
	}
	
    // 构造根节点值
	int num = 0;
	while (*s != ',') {
		num = num * 10 + (*s - '0');
		++s;
	}
	++s; 
    // 递归构造树
	TreeNode *root = new TreeNode(num);
	root-&gt;left = deseri(s);
	root-&gt;right = deseri(s);

	return root;
}

TreeNode* Deserialize(char *str) {
	return deseri(str);
}

所以，最终的代码如下：

class Solution {
public:
    char* Serialize(TreeNode *root) {    
        if (!root) {
            return "#";
        }
        string res = to_string(root->val);
        res.push_back(',');
        char* left = Serialize(root->left);
        char* right = Serialize(root->right);
        char* ret = new char[strlen(left)+strlen(right)+res.size()];
        // 如果是string类型，直接用operator += ,这里char* 需要用函数
        strcpy(ret,res.c_str());
        strcat(ret,left);
        strcat(ret,right);
        return ret;
    }
    TreeNode* deseri(char *&s) {
        if (*s == '#') {
            ++s;
            return nullptr;
        }
        // 构造根节点值
        int num = 0;
        while (*s != ',') {
            num = num * 10 + (*s - '0');
            ++s;
        }
        ++s; 
        // 递归构造树
        TreeNode *root = new TreeNode(num);
        root->left = deseri(s);
        root->right = deseri(s);
        return root;
    }

    TreeNode* Deserialize(char *str) {
        return deseri(str);
    }
};

中序遍历，后序遍历大致都差不多。

##方法二：层次遍历实现层次遍历采用队列实现。跟先序遍历的思想差不多，无非都是把树的所有数据遍历一遍，然后记录下来。层次遍历模板：

void bfs(TreeNode *root){
    queue<treenode*> qt;
    qt.push(root);
 	string s;
    while (!qt.empty())
    {
    	// pop operator
        TreeNode *node = qt.front();
        qt.pop();

        // process node
        if (node == NULL)
        {
            s.push_back('#');
            s.push_back(',');
            continue;
        }
        s += to_string(node-&gt;val);
        s.push_back(',');

        // push operator
        qt.push(node-&gt;left);
        qt.push(node-&gt;right);
 
    }
}

序列化的操作直接根据模板套即可。代码如下：

char* Serialize(TreeNode *root)
    {
        string s;
        queue<TreeNode*> qt;
        qt.push(root);

        while (!qt.empty())
        {
            // pop operator
            TreeNode *node = qt.front();
            qt.pop();
            // process null node
            if (node == nullptr)
            {
                s.push_back('#');
                s.push_back(',');
                continue;
            }
            // process not null node
            s += to_string(node->val);
            s.push_back(',');
            // push operator
            qt.push(node->left);
            qt.push(node->right);

        }

        char *ret = new char[s.length() + 1];
        strcpy(ret, s.c_str());

        return ret;
    }

反序列化就是根据层次遍历在走一遍即可。代码如下：

    TreeNode* Deserialize(char *str)
    {
        if (str == nullptr) {
            return nullptr;
        }
        // 可用string成员函数
        string s(str);
        if (str[0] == '#') {
            return nullptr;
        }

        // 构造头结点
        queue<TreeNode*> nodes;
        TreeNode *ret = new TreeNode(atoi(s.c_str()));
        s = s.substr(s.find_first_of(',') + 1);
        nodes.push(ret);
        // 根据序列化字符串再层次遍历一遍，来构造树
        while (!nodes.empty() && !s.empty())
        {
            TreeNode *node = nodes.front();
            nodes.pop();
            if (s[0] == '#')
            {
                node->left = nullptr;
                s = s.substr(2);
            }
            else
            {
                node->left = new TreeNode(atoi(s.c_str()));
                nodes.push(node->left);
                s = s.substr(s.find_first_of(',') + 1);
            }

            if (s[0] == '#')
            {
                node->right = nullptr;
                s = s.substr(2);
            }
            else
            {
                node->right = new TreeNode(atoi(s.c_str()));
                nodes.push(node->right);
                s = s.substr(s.find_first_of(',') + 1);
            }
        }
        return ret;
    }

所以，最终的代码是：

class Solution {
public:
    char* Serialize(TreeNode *root)
    {
        string s;
        queue<TreeNode*> qt;
        qt.push(root);

        while (!qt.empty())
        {
            // pop operator
            TreeNode *node = qt.front();
            qt.pop();
            // process null node
            if (node == nullptr)
            {
                s.push_back('#');
                s.push_back(',');
                continue;
            }
            // process not null node
            s += to_string(node->val);
            s.push_back(',');
            // push operator
            qt.push(node->left);
            qt.push(node->right);

        }

        char *ret = new char[s.length() + 1];
        strcpy(ret, s.c_str());

        return ret;
    }
    TreeNode* Deserialize(char *str)
    {
        if (str == nullptr) {
            return nullptr;
        }
        // 可用string成员函数
        string s(str);
        if (str[0] == '#') {
            return nullptr;
        }

        // 构造头结点
        queue<TreeNode*> nodes;
        TreeNode *ret = new TreeNode(atoi(s.c_str()));
        s = s.substr(s.find_first_of(',') + 1);
        nodes.push(ret);
        // 根据序列化字符串再层次遍历一遍，来构造树
        while (!nodes.empty() && !s.empty())
        {
            TreeNode *node = nodes.front();
            nodes.pop();
            if (s[0] == '#')
            {
                node->left = nullptr;
                s = s.substr(2);
            }
            else
            {
                node->left = new TreeNode(atoi(s.c_str()));
                nodes.push(node->left);
                s = s.substr(s.find_first_of(',') + 1);
            }

            if (s[0] == '#')
            {
                node->right = nullptr;
                s = s.substr(2);
            }
            else
            {
                node->right = new TreeNode(atoi(s.c_str()));
                nodes.push(node->right);
                s = s.substr(s.find_first_of(',') + 1);
            }
        }
        return ret;
    }
};

此题主要考察对树的遍历和构造树。</treenode*></treenode*></treenode*>

全部评论

推荐最新楼层

布丁不太咸

上海交通大学 Java

我就想知道为什么非要char*

5 回复分享

发布于 2020-12-13 13:29

Antrn

西安电子科技大学 Java

我想知道为啥层次遍历通不过。。。

3 回复分享

发布于 2020-11-27 17:02

wulimmya

电子科技大学 C++

弱弱地提问：为什么先序遍历序列化函数中不用delete释放left和right啊，如果left和right的长度大于1，则是由上一级调用中new的内存，在这一级中又new了新的内存，并把left和right都复制过去了，就可以把left和right的内存释放掉了吧。不是说有new就要时刻记得delete吗，char指针是常规指针，不是对象，没有析构函数自动释放占用的内存，这样难道不是会造成内存泄漏吗？一直对内存问题不太懂，希望得到指点，谢谢大佬，不明白为什么不需要释放，而且释放了反而出错

点赞回复分享

发布于 2020-06-24 11:36

牛客793257260号

重庆邮电大学 Java

如果你释放掉了，那原有的数据就会丢失。

1 回复分享

发布于 2020-07-20 21:40

菜得不行的小宝

网易互娱_图形开发工程师

很奇怪为什么反系列化没有判断指针到达'\0'的判断。。。有大佬解惑吗

1 回复分享

发布于 2020-08-03 20:52