If you’re not familiar with data structures, take a look: A swastika explanation of data structures

Reference to Offer series

Brush question warehouse

37. Serialize binary trees

Topic describes

Implement two functions to serialize and deserialize the binary tree

The serialization of binary tree means that the result of a binary tree traversed in a certain way is saved as a string in a certain format, so that the binary tree built in memory can be persisted. Serialization can be modified based on a binary tree traversal of order first, middle, last, and layer. The result of serialization is a string, denoted by some symbol for the empty node (#), starting with! Denotes the end of a node value (value!). .

Deserialization of binary tree is to reconstruct the binary tree according to the serialized string STR obtained in a certain traversal order.

For example, we could serialize a binary tree with only a root node of 1 as “1,” and then parse back to the binary tree example 1 through our own function

The input

,6,10,5,7,9,11 {8}

The return value

,6,10,5,7,9,11 {8}

Ideas & Solutions

Serialization: Make the call sequential traversal, that is, traversal the root node, then left, left, and right nodes, using recursion. If it is empty, it is replaced by “#” and separated by “, “.

Deserialization: split by comma, using index as index, +1 each time, again using recursion, first root node, then left node, then right node.

import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    int index = -1;
    String Serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if(root == null) {
            sb.append(# ",");
            return sb.toString();
        }
        sb.append(root.val + ",");
        sb.append(Serialize(root.left));
        sb.append(Serialize(root.right));
        return sb.toString();
    }

    TreeNode Deserialize(String str) {
        index++;
        String[] strs = str.split(",");
        TreeNode node = null;
        if(! strs[index].equals("#")) {
            node = new TreeNode(Integer.valueOf(strs[index]));
            node.left = Deserialize(str);
            node.right = Deserialize((str));
        }
        returnnode; }}Copy the code

The C++ code is as follows:

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()];

        strcpy(ret, res.c_str());
        strcat(ret, left);
        strcat(ret, right);
        return ret;
    }

    TreeNode *deseri(char *&str) {
        if (*str == The '#') {
            ++str;
            return nullptr;
        }

        int num = 0;
        while(*str ! =', ') {
            num = num * 10 + (*str - '0');
            ++str;
        }
        ++str;
        TreeNode *root = new TreeNode(num);
        root->left = deseri(str);
        root->right = deseri(str);
        return root;
    }

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

[Author profile] : Qin Huai, public number [Qin Huai grocery store] author, personal website: aphysia.cn, the road of technology is not at that time, mountain high water long, even if slow, chi and not stop.

Offer all questions in PDF

Open Source Programming Notes