剑指 Offer 37. 序列化二叉树

题目链接：剑指 Offer 37. 序列化二叉树

取巧做法

class Codec {
private:
    TreeNode* root;
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        this->root = root;
        return "";
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        return this->root;
    }
};

方法一：后序遍历实现

解题思路

将树后续遍历为字符串保存，并记录每个节点的左右子树的节点个数，然后取序列最后一个数为根节点，通过其左右子树的节点个数，递归的\(build\)其左右子树。

代码

class Codec {
private:
    vector<vector<int>> childNum; // 用于对后序遍历序列进行反序列化过程中判断当前根节点的左右子树集合
public:
    string postorder(TreeNode* root, int &leftNum, int &rightNum) {
        string left, right;
        int child_1_left_num = 0, child_1_right_num = 0;
        int child_2_left_num = 0, child_2_right_num = 0;
        if (root->left) {
            left = postorder(root->left, child_1_left_num, child_1_right_num);
            leftNum ++ ;
        }
        if (root->right) {
            right = postorder(root->right, child_2_left_num, child_2_right_num);
            rightNum ++ ;
        }
        leftNum += child_1_left_num + child_1_right_num;
        rightNum += child_2_left_num + child_2_right_num;
        childNum.push_back({leftNum, rightNum});
        if (left.length() != 0) left += ",";
        if (right.length() != 0) right += ",";
        return left + right + to_string(root->val);
    }

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (!root) return "";
        int leftNum = 0, rightNum = 0;
        return postorder(root, leftNum, rightNum);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.length() == 0) return NULL;
        int n = data.size();
        vector<int> value;
        for (int i = 0, j = 0; i < n; i = j + 1, j = i ) { // string转换为数组
            while (j < n) {
                if (data[j] == ',') break;
                j ++ ;
            }
            value.push_back(stoi(data.substr(i, j - i)));
        }
        // build tree
        function<TreeNode*(int, int)> build = [&](int l, int r) -> TreeNode* {
            if (l > r) return NULL;
            int mid = l + childNum[r][0] - 1;
            TreeNode* root = new TreeNode(value[r]);
            root->left = build(l, mid);
            root->right = build(mid + 1, r - 1);
            return root;
        };
        return build(0, value.size() - 1);
    }
};

复杂度分析

时间复杂度：\(O(n)\)，\(n\)为节点个数；
空间复杂度：\(O(n)\)，递归栈空间 和 \(childNum\)数组。

方法二：层序遍历实现

解题思路

先对树进行层序遍历，在遍历的过程中，叶子节点的左右空节点也加入序列中；然后在进行层序遍历构造树，维护一个指针\(i\)，指向当前节点的孩子节点。

代码

class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (!root) return "";
        string str;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* front = q.front();
            q.pop();
            if (str.length() != 0) str += ",";
            if (!front) str += "#";
            else {
                str += to_string(front->val);
                q.push(front->left);
                q.push(front->right);
            }
        }
        return str;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.length() == 0) return NULL;
        int i = 0, idx = data.find_first_of(",", i);
        TreeNode* root = new TreeNode(stoi(data.substr(i, idx - i)));
        i = idx + 1 ;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* front = q.front();
            q.pop();
            idx = data.find_first_of(",", i);
            front->left = data.substr(i, idx - i) == "#" ? NULL : new TreeNode(stoi(data.substr(i, idx - i)));
            i = idx + 1;
            idx = data.find_first_of(",", i);
            front->right = data.substr(i, idx - i) == "#" ? NULL : new TreeNode(stoi(data.substr(i, idx - i)));
            i = idx + 1;
            if (front->left != NULL) q.push(front->left);
            if (front->right != NULL) q.push(front->right);
        }
        return root;
    }
};

复杂度分析

时间复杂度：\(O(n)\)，\(n\)为节点个数；
空间复杂度：\(O(n)\)，队列空间。