剑指 Offer 37 序列化二叉树

标签: 剑指 Offer 发布于:2022-02-26 13:03:36 编辑于:2022-02-26 13:03:36 浏览量:900

概述

https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

前序遍历

下面的实现不是很好看,其实用队列更好一些,而且里面直接存节点指针,这样就不需要用 INT_MAX 来标记了。

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (!root) return "#,";
        return to_string(root->val) + "," + serialize(root->left) + serialize(root->right);
    }

    vector<int> arr;
    int i;
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        arr = {};
        i = 0;
        string t;
        for (auto c : data) {
            if (c == ',') {
                if (t == "#") {
                    arr.push_back(INT_MAX);
                } else {
                    arr.push_back(stoi(t));
                }
                t = "";
            } else {
                t += c;
            }
        }
        return helper();
    }

    TreeNode* helper() {
        if (arr[i] == INT_MAX) {
            i ++;
            return nullptr;
        }
        auto root = new TreeNode(arr[i]);
        i ++;
        root->left = helper();
        root->right = helper();
        return root;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/