【数据结构】搜索二叉树(BST)和普通二叉树的序列化与反序列化

背景

算法题中经常会用到二叉树的结构：

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

为了构造一些测试用例，有些人会写这样的代码来建立BST：

TreeNode* p = new TreeNode(1);

p->left = new TreeNode(2);

TreeNode* p2 = p->left;

p2->left = new TreeNode(3);

...

这样写不是不行，就是在构造复杂用例的时候不方便。其实对于二叉树可以有更方便的构建方法，相信在二叉树相关的题目中我们已经接触过了。这个可以用两个树的遍历序列来做，如先序遍历和后序遍历序列构造唯一的二叉树。但是这个仅针对于BST, 因为它的各元素唯一，所以可以用先序后序确定。

对于元素可以不唯一的二叉树，例如1,2,2则要用另外一个方法来构建了。

序列化与反序列化

序列化技术可以将数据对象转换为可持久化存储或可网络传输的数据。这里采用序列化方式为：

1.对BST树取先序和后序遍历，得到数组；

2.数组再转为可以区分的字符串。

反序列化方式为：

1.根据字符串得到先序和后序遍历数组;

2.根据1中序列建立树。

这里忽略数组到字符串的转换。

BST的反序列化

BST的序列可以构造如下：

    TreeNode* buildTree(vector<int>& P, vector<int>& T) {
        if (P.size() != T.size()) return NULL;
        int len = P.size();
        TreeNode* root = helper(P, T, 0, len - 1, 0, len - 1);
        return root;
    }
    TreeNode* helper(vector<int>& P, vector<int>& T, int pt, int pd, int st, int ed) {
        if (st > ed) return NULL;
        TreeNode* root = new TreeNode(0);
        int val = P[pt], len = P.size();
        for (int i = st; i <= ed; i++) {
            if (T[i] == val) {
                root->left = helper(P, T, pt + 1, pt + i - st, st, i - 1);
                root->val = val;
                root->right = helper(P, T, pt + i - st + 1, pd, i + 1, ed);
                break;
            }
        }
        return root;
    }

普通二叉树

1.层次遍历(Level Order Traversal)表示法

除非空节点外，均以节点内的值表示节点，空节点用#表示。

2.序列化+反序列化流程与代码

序列化用：用一个队列，层次遍历，组成一个字符串

反序列化：将字符串先解析成vector<TreeNode*>（不用vector<int>当然是因为二叉树中不能用特殊值来代表空节点,比如用-1的话就不能用-1了），再构建相应的TreeNode* root

static TreeNode* __buildLevelTree(vector<TreeNode*>& vec) {
    int size = vec.size();
    if (size == 0) return NULL;
    vector<TreeNode*> tvec(size);
    for (int i = 0; i < size; i++) {
        if (vec[i] != NULL) {
            tvec[i] = new TreeNode(vec[i]->val);
        }
    }
    int j = 1;
    for (int i = 0; j < size; i++) {
        if (tvec[i] != NULL) {
            tvec[i]->left = tvec[j++];
            if (j < size) {
                tvec[i]->right = tvec[j++];
            }
        }
    }
    return tvec[0];
}


string serializeLevelTree(TreeNode* root) {
    if (root == NULL) return "";
    queue<TreeNode*> q;
    q.push(root);
    string s;
    while (!q.empty()) {
        TreeNode* cur = q.front();
        q.pop();
        if (cur != NULL) {
            q.push(cur->left);
            q.push(cur->right);
            char val[16];
            sprintf(val, "%d", cur->val);
            s.append(val);
            s.append(1, ',');
        } else {
            s.append("#,");
        }
    }
    if (s.size() > 0) {
        s.resize(s.size() - 1);
    }
    return s;
}

TreeNode* deserializeLevelTree(const string& s) {
    vector<TreeNode*> vec;
    int size = s.size();
    int val = 0, st = 0;
    for (int i = 0; i < size; i++) {
        if (s[i] == ',' && i > st) {
            const char* str = s.substr(st, i - st).c_str();
            if (!strcmp(str, "#")) {
                vec.push_back(NULL);
                st = i + 1;
                continue;
            }
            st = i + 1;
            val = strtol(str, NULL, 10);
            TreeNode* newnode = new TreeNode(val);
            vec.push_back(newnode);
        }
    }
    TreeNode* root = __buildLevelTree(vec);
    // free_tree(root); //to avoid memory leak
    return root;
}


int main() {
    string s;
    TreeNode* res = deserializeLevelTree("3,1,#,4,#,#,#");
    s = serializeLevelTree(res);
    cout << s << endl; //if input is 3,1,#,4,#,#[without last #],
    it will be auto-completed to 3,1,#,4,#,#,#

    res = new TreeNode(10);
    res->left = new TreeNode(101);
    res->left->right = new TreeNode(102);
    s = serializeLevelTree(res);
    cout << s << endl; // out: 10,101,#,#,102,#,#
    // TreeNode* root = buildTree(res);
    return 0;
}

References:

[1]序列化二叉树（层次遍历）

https://blog.csdn.net/wangdongli_1993/article/details/82192341

[2] Leetcode N-ary Tree Level Order Traversal