【二叉树专题】剑指 Offer 37. 序列化二叉树-跟着帅地玩副业，开拓第二曲线PlayOffer

ppopp 普通 2023年8月25日上午1:19

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
@Freeich 对的，如果不是字面量的拼接，使用的就是StringBuilder。String s = s1+s2;对应的就是StringBuilder sb = new StringBuilder(),sb.append(s1),sb.append(s2)。然后返回时调用sb.toString()，这个toString()一般来说看源码的话就是new String()，这样一来新建了一个String对象，所以占用内存
*/
using namespace std;

class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string res = “”;
if(!root) return “”;
queue<TreeNode> q;
q.push(root);
TreeNode cur = new TreeNode(0);
while(!q.empty()){
int len = q.size();
while(len–){
cur = q.front();
q.pop();
if(!cur){
res.push_back(‘$’);
}else{
res.append(to_string(cur->val));
}
res.push_back(‘,’);
if(cur!=nullptr){
q.push(cur->left);
q.push(cur->right);
}
}
}
res.pop_back();
return res;

}


// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
    if(data.size()==0)  return nullptr;
    int len = data.size();
    int i = 0;
    vector<TreeNode*> vec;
    while(i < len){
        string str = "";
        while(i < len && data[i] != ','){
            str.push_back(data[i]);
            i++;
        }

        if(str == "$"){
            TreeNode *temp = nullptr;
            vec.push_back(temp);
        }else{
            int temp = stoi(str);
            TreeNode* cur = new TreeNode(temp);
            vec.push_back(cur);
        }
        i++;
    }
    int j = 1;
    for(int i = 0; j < vec.size(); i++){
        if(vec[i] == nullptr) continue;
        if(j<vec.size()) vec[i]->left = vec[j++];
        if(j<vec.size()) vec[i]->right = vec[j++];
    }
    return vec[0];
}

};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

0 赞同 0 条回复

hi 普通 2023年8月14日上午9:54

前序遍历二叉树把节点存储为字符串
解密中如何把字符串中的字符分割开来

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    //利用前序遍历加密二叉树
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res;
        dfs_s(root, res);
        return res;
    }

    void dfs_s(TreeNode* p, string &res){
        if(p == NULL){
            res += "null ";
            return;
        } 
        res += to_string(p -> val) + ' ';
        dfs_s(p -> left, res);
        dfs_s(p -> right, res);
    }

    //利用前序遍历的二叉树特点解密字符串
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int u = 0; 
        return dfs_d(data, u);
    }

    TreeNode* dfs_d(string data, int &u){
        int k = u;
        while(data[k] != ' ') k++;
        if(data[u] == 'n'){
           u = k + 1;
           return NULL; 
        } 
        int val = 0, sign = 1;
        if(u < k && data[u] == '-') sign = -1, u++;
        for(int i = u; i < k; i++) val = val* 10 + data[i] - '0'; 
        val *= sign;
        u = k + 1;
        TreeNode* root = new TreeNode(val);
        root -> left = dfs_d(data, u);
        root -> right = dfs_d(data, u);
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

0 赞同 0 条回复

山川湖海普通 2023年8月3日下午10:09

class Codec {
public:

// Encodes a tree to a single string.
string serialize(TreeNode* root) {
    string res;
    if (!root) return res;
    queue<TreeNode*> que;
    que.push(root);
    while (!que.empty()) {
        TreeNode* front = que.front();
        que.pop();
        if (front != nullptr) {
            res += to_string(front->val) + ",";
            que.push(front->left);
            que.push(front->right);
        }
        else {
            res += "null,";
        }

    }
    return res;
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
    if (data.empty()) return nullptr;
    vector<string> s = split(data);

    queue<TreeNode*> que;
    TreeNode* root = new TreeNode(stoi(s[0]));
    que.push(root);
    int i = 1; // 因为这里root已经被处理了，所以i从1开始

    while (!que.empty()) {
        TreeNode* front = que.front();
        que.pop();
        if (s[i] != "null") {
            front->left = new TreeNode(stoi(s[i]));
            que.push(front->left);
        }
        i++;
        if (s[i] != "null") {
            front->right = new TreeNode(stoi(s[i]));
            que.push(front->right);
        }
        i++;
    }
    return root;
}

vector<string> split(string& s) {
    // cout << s << endl;
    vector<string> res;
    int n = s.size();
    int i = 0;

    while (i < n) {
        int j = i + 1;
        while (j < n && s[j] != ',') j++;
        res.push_back(s.substr(i, j - i));
        i = j + 1;
    }
    return res;
}

};

0 赞同 0 条回复

doordie. 普通 2023年7月28日上午11:28

序列化：
打印null值的层序遍历
反序列化：通过队列一层一层构建二叉树

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return "[]";

        // 返回的字符串
         StringBuilder res = new StringBuilder("[");
        // 辅助队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            // 如果该节点不为null，添加val到返回结果,并继续遍历
            if(node != null){
                res.append(node.val + ",");  
                queue.add(node.left);
                queue.add(node.right);   
            // 如果该节点为空，      
            }else{
                res.append("null,");
            }   


        }
     // 删掉最后一个逗号，并加上括号
        res.deleteCharAt(res.length() - 1);
        res.append("]");
         return res.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        //1.特例处理
        if(data.equals("[]")) return null;
        //2.初始化
        Queue<TreeNode> queue = new LinkedList<>();  //辅助队列
        int i = 1; //指针
        String[] vals = data.substring(1, data.length() - 1).split(","); //字符串数组
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        queue.add(root);
        //3.按层构建
        while(!queue.isEmpty()){
            //3.1 节点出队
            TreeNode node = queue.poll();
            //3.2 构建node的左孩子节点 如果val不为null  值为vals[i]，并入队
            if(!vals[i].equals("null")){
                node.left = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.left);
            }
            i++;
             //3.3 构建node的右孩子节点 如果val不为null  值为vals[i]，并入队
             if(!vals[i].equals("null")) {
                node.right = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.right);
            }
            i++;

        }
             return root;   
    }
}

0 赞同 0 条回复

北辰普通 2023年7月24日下午9:25

public class Codec {

   // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        return rseriablize(root,"");
    }

    public String rseriablize(TreeNode root,String str) {
        if(root==null) return str+="null,";
        else{
            str+=str.valueOf(root.val)+",";
            str = rseriablize(root.left,str);
            str = rseriablize(root.right,str);
        }
        return str;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] dataArray = data.split(",");
        List<String> dataList = new LinkedList<String>(Arrays.asList(dataArray));
        return rdeserialize(dataList);
    }

    public TreeNode rdeserialize(List<String> dataList) {
        if(dataList.size()==0) return null;
        if(dataList.get(0).equals("null")) {
            dataList.remove(0);
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(dataList.get(0)));
        dataList.remove(0);
        root.left = rdeserialize(dataList);
        root.right = rdeserialize(dataList);
        return root;
    }
}

时间复杂度：O（n）
空间复杂度：O（n）

0 赞同 0 条回复

今天你刷题了嘛普通 2023年7月23日下午9:27

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        // 使用层序遍历，但要保存空节点
        if(root==null) return "";
        StringBuilder build = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode temp = queue.poll();
            if(temp!=null){
                // 空节点也需要入队
                queue.offer(temp.left);
                queue.offer(temp.right);
                build.append(temp.val + ",");
            } else{
                build.append("null,");
            }
        }
        // 只需要实现序列化和反序列化，并不需要格式和leetcode一样
        // 这里的格式会是 1，2，3，null, null, 4,5,null,null,null,null,
        return build.toString();        
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data==null||data.length()<=0) return null;
        String[] s = data.split(",");
        Queue<TreeNode> queue = new LinkedList();
        TreeNode root = new TreeNode(Integer.parseInt(s[0]));
        queue.add(root);
        int i=1;
        while(!queue.isEmpty()){
            TreeNode temp = queue.poll();
            //  构建左节点
            if(!s[i].equals("null")){
                TreeNode left = new TreeNode(Integer.parseInt(s[i]));
                temp.left = left;
                queue.offer(left);
            }
            i++;
            // 构建右节点
            if(!s[i].equals("null")){
                TreeNode right = new TreeNode(Integer.parseInt(s[i]));
                temp.right = right;
                queue.offer(right);
            }
            i++;

        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

时间复杂度：O（n）
空间复杂度：O（n）

0 赞同 0 条回复

片言莫语普通 2023年7月22日下午4:09

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        // 序列化成字符串,1,2,3,null,null,4,5,null...
        if(root == null){
            return "";
        }
        StringBuilder build = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while(!queue.isEmpty()){
            TreeNode t = queue.poll();
            if(t != null){
                queue.add(t.left);
                queue.add(t.right);
                build.append(t.val + ",");
            }else{
                build.append("null,");
            }
        }

        return build.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        // 1,2,3,null,null,4,5,null...
        if(data == null || data.length() <= 0){
            return null;
        }
        String[] s = data.split(",");
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(s[0]));
        queue.add(root);
        int i = 1;
        while(!queue.isEmpty()){
            TreeNode t = queue.poll();
            // 构建做左节点
            if(!s[i].equals("null")){
                TreeNode left = new TreeNode(Integer.parseInt(s[i]));
                t.left = left;
                queue.add(left);
            }
            i++;
            // 构建右节点
            if(!s[i].equals("null")){
                TreeNode right = new TreeNode(Integer.parseInt(s[i]));
                t.right = right;
                queue.add(right);
            }
            i++;
        }
        return root;

    }
}

0 赞同 0 条回复

普通 2023年7月20日下午11:43

java 有点取巧了
public class Codec {
private TreeNode root;
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
this.root =root;
return null;
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    return root;
}

}

0 赞同 1 条回复

doordie. 普通 @ 2023年7月28日上午11:44

好意思吗哈哈哈

登录以回复

Marshan 普通 2023年7月19日下午10:01

最后两个测试用例没有通过

class Codec {
public:

    // Encodes a tree to a single string.
    string res;
    string serialize(TreeNode* root) {
        if(!root){
            return "#";
        }
        queue<TreeNode*> queue;
        queue.push(root);
        while(!queue.empty()){
            TreeNode* tmp = queue.front();
            queue.pop();
            if(tmp){
                res += ('0' + tmp->val);
                queue.push(tmp->left);
                queue.push(tmp->right);
            }
            else{
                res += '#';
            }
        }
        cout<<res;
        return res;
    }
    TreeNode* root = nullptr;
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        TreeNode *root = nullptr;

        root = helper(root,data);
        return root;
    }
    TreeNode* helper(TreeNode *root,string& data){
        if(data.size() == 1){
            return nullptr;
        }
        int i = 0;
        root = new TreeNode(data[i] - '0');
        i++;
        queue<TreeNode *>queue;
        queue.push(root);
        while(i < data.size()-1){
            TreeNode *tmp = queue.front();
            queue.pop();
            char c1 = data[i];
            char c2 = data[i+1];
            if(c1 != '#'){
                tmp->left = new TreeNode(c1 - '0');
                queue.push(tmp->left);
            }
            if(c2 != '#'){
                tmp->right = new TreeNode(c2 - '0');
                queue.push(tmp->right);
            }

            i += 2;
        }
        return root;
    }
};

0 赞同 0 条回复

Mby 普通 2023年7月19日下午4:58

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        //序列化成字符串，1，2，3，null，null，4，5，null...
        if(root == null){
            return "";
        }
        StringBuilder bulid = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while(!queue.isEmpty()){
            TreeNode t = queue.poll();
            if(t != null){
                queue.add(t.left);
                queue.add(t.right);
                bulid.append(t.val + ",");
            }else{
                bulid.append("null,");
            }
        }
        return bulid.toString();

    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null || data.length() <= 0){
            return null;
        }
        String [] s = data.split(",");
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(s[0]));
        queue.add(root);
        int i = 1;
        while(!queue.isEmpty()){
            TreeNode t = queue.poll();
            //构建左节点
            if(!s[i].equals("null")){
                TreeNode left = new TreeNode(Integer.parseInt(s[i]));
                t.left = left;
                queue.add(left);
            }
            i++;
            //构建右节点
            if(!s[i].equals("null")){
                TreeNode right = new TreeNode(Integer.parseInt(s[i]));
                t.right = right;
                queue.add(right);
            }
            i++;
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

0 赞同 0 条回复

枫梓。普通 2023年7月19日下午3:40

class Codec {
private:
    queue<string> que;
    void GetData(string s) {
        stringstream s_stream(s);
        while(s_stream.good()) {
            string substr;
            getline(s_stream, substr, ',');
            que.push(substr);
       }
    }
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string str;
        queue<TreeNode*> q;
        if(!root) return "[]";
        q.push(root);
        int height = 1;
        while(!q.empty()){
            int size = q.size();
            for(int i = 0; i < size; ++i) {
                root = q.front();
                q.pop();
                if(root == nullptr){
                    str += "null,";
                    continue;
                }
                str += to_string(root->val) + ",";
                q.push(root->left);
                q.push(root->right);
            }
            ++height;
        }
        str.pop_back();
        return str;
    }


    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data == "[]") return NULL;
        GetData(data);
        TreeNode* root = new TreeNode(stoi(que.front()));
        que.pop();
        int height = 1;
        queue<TreeNode*> node;
        node.push(root);
        while(!que.empty()) {
            TreeNode *cur = node.front(); node.pop();
            string lt = que.front(); que.pop();
            string rt = que.front(); que.pop();
            if(lt != "null") {
                TreeNode* temp = new TreeNode(stoi(lt));
                cur->left = temp;
                node.push(temp);
            } else {
                cur->left = nullptr;
            }
            if(rt != "null") {
                TreeNode* temp = new TreeNode(stoi(rt));
                cur->right = temp;
                node.push(temp);
            } else {
                cur->right = nullptr;
            }
        }
        return root;
    }
};

字符串操作还得记一下

0 赞同 0 条回复

Mooby 普通 2023年7月19日上午10:01

十一
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
    if (root == null) return "[]";
    StringBuilder res = new StringBuilder("[");
    Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node != null) {
            res.append(node.val + ",");
            queue.add(node.left);
            queue.add(node.right);
        } else {
            res.append("null,");
        }
    }
    res.deleteCharAt(res.length() - 1);
    res.append("]");
    return res.toString();
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    if (data.equals("[]")) return null;
    String[] vals = data.substring(1, data.length() - 1).split(",");
    TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
    Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
    int i = 1;
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (!vals[i].equals("null")) {
            node.left = new TreeNode(Integer.parseInt(vals[i]));
            queue.add(node.left);
        }
        i++;
        if (!vals[i].equals("null")) {
            node.right = new TreeNode(Integer.parseInt(vals[i]));
            queue.add(node.right);
        }
        i++;
    }
    return root;
}

}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

0 赞同 0 条回复

波雅汉库克普通 2023年7月19日上午8:03

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string str;
        if(root == nullptr){
            return str;
        }
        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty()){
            root = q.front();
            q.pop();
            if(root == nullptr){
                str += "null,";
                continue;
            }
            str += to_string(root->val) + ",";
            q.push(root->left);
            q.push(root->right);
        }
        str.pop_back();
        return str;
    }
    void getData(string data, deque<string>& strs){
        stringstream s_stream(data); //create string stream from the string
        while(s_stream.good()) {
            string substr;
            getline(s_stream, substr, ','); //get first string delimited by comma
            strs.push_back(substr);
       }
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.empty()){
            return nullptr;
        }  
        deque<string> strs;
        getData(data, strs);
        TreeNode* root = new TreeNode(stoi(strs.front()));
        queue<TreeNode*> q;
        TreeNode* cur = root;
        q.push(cur);
        strs.pop_front();
        while(!strs.empty()){
            cur = q.front();
            q.pop();
            string left = strs.front();
            strs.pop_front();
            string right = strs.front();
            strs.pop_front();
            if(left == "null"){
                cur->left = nullptr;
            }
            else{
                TreeNode* leftNode = new TreeNode(stoi(left));
                q.push(leftNode);
                cur->left = leftNode;
            }
            if(right == "null"){
                cur->right = nullptr;
            }
            else{
                TreeNode* rightNode = new TreeNode(stoi(right));
                q.push(rightNode);
                cur->right = rightNode;
            }
        }
        return root;
    }
};

时间：O（n)
空间：O（n）

0 赞同 0 条回复

#00456B 普通 2023年7月19日上午12:11

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:

string SEP = ",";
string EMPTY = "#";//这里就用单个字符，否则会超时
// Encodes a tree to a single string.
//序列化，这里用前序遍历
//主函数
string serialize(TreeNode* root) {
    string ans = "";
    serialize(root, ans);
    return ans;
}
//辅助函数
void serialize(TreeNode* root, string& ans){
    if(root == NULL){
        ans += EMPTY + SEP;
        return ;
    }
    //===============
    //preorder
    ans += to_string(root->val) + SEP;
    //===============
    serialize(root->left, ans);
    serialize(root->right, ans);
}

// Decodes your encoded data to tree.
//反序列化，也是前序遍历
//主函数
TreeNode* deserialize(string data) {
    cout<<data<<endl;
    vector<string> nodes;
    string str = "";//记录每一个节点的值
    for(auto c : data){
        if(c == SEP[0]){
            nodes.push_back(str);
            str = "";
        }
        else{
            str += c;
        }
    }
    for(auto x:nodes){
        cout<<x<<' ';
    }
    cout<<endl;
    return deserialize(nodes);
}
//辅助函数
TreeNode* deserialize(vector<string>& nodes){
    if(nodes.empty()){
        return NULL;
    }
    //===============
    //preorder
    string temp = nodes[0];
    nodes.erase(nodes.begin());
    if(temp == EMPTY){
        return NULL;
    }
    TreeNode* root = new TreeNode(stoi(temp));
    //===============
    root->left = deserialize(nodes);
    root->right = deserialize(nodes);
    return root;
}

};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

0 赞同 0 条回复

周小二普通 2023年7月19日上午12:04

//序列化反序列化
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) {
            return "[]";
        }
        Queue<TreeNode> queue = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        TreeNode node;
        queue.add(root);
        while(!queue.isEmpty()) {
            node = queue.poll();
            if(node != null) {
                sb.append(node.val + ",");
                queue.add(node.left);
                queue.add(node.right);
            } else{
                sb.append("null,");
            }
        }
        sb.deleteCharAt(sb.length() - 1);
        sb.append("]");
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == "[]") {
            return null;
        }
        String[] vars = data.substring(1, data.length() - 1).split(",");
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(vars[0]));
        queue.add(root);
        int i = 1;
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(!vars[i].equals("null")) {
                node.left = new TreeNode(Integer.parseInt(vars[i]));
                queue.add(node.left);
            }
            i++;
            if(!vars[i].equals("null")) {
                node.right = new TreeNode(Integer.parseInt(vars[i]));
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }
}

0 赞同 0 条回复

CaCO3 永久会员 2023年7月18日下午9:54

”’java
public class Codec {

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
    return rserialize(root,"");
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    String[] dataArray = data.split(",");
    List<String> dataList = new LinkedList<String>(Arrays.asList(dataArray));
    return rdeserialize(dataList);
}

public String rserialize(TreeNode root,String str){
    if(root == null){
        str += "None,";
    }else{
        str += String.valueOf(root.val)+",";
        str = rserialize(root.left,str);
        str = rserialize(root.right,str);
    }
    return str;
}
public TreeNode rdeserialize(List<String> dataList){
    if(dataList.get(0).equals("None")){
        dataList.remove(0);
        return null;
    }
    TreeNode root = new TreeNode(Integer.valueOf(dataList.get(0)));
    dataList.remove(0);
    root.left = rdeserialize(dataList);
    root.right = rdeserialize(dataList);
    return root;
}

}
时间复杂度O(n)
空间复杂度O(n)
”’

0 赞同 0 条回复

土豆芋泥包_ 普通 2023年7月18日下午9:17

代码

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root==null){
            return "";
        }
        StringBuilder builder = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode t = queue.poll();
            if(t!=null){
                queue.add(t.left);
                queue.add(t.right);
                builder.append(t.val+",");
            }else{
                builder.append(null+",");
            }
        }
        return builder.toString();
    } 



    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data==null||data.length()<=0){
            return null;
        }
        String[] s = data.split(",");
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(s[0]));
        queue.add(root);
        int i = 1;
        while(!queue.isEmpty()){
            TreeNode t = queue.poll();
            if(!s[i].equals("null")){
                TreeNode left = new TreeNode(Integer.parseInt(s[i]));
                t.left = left;
                queue.add(left);
            }
            i++;
            if(!s[i].equals("null")){
                TreeNode right = new TreeNode(Integer.parseInt(s[i]));
                t.right = right;
                queue.add(right);
            }
            i++;
        }
        return root;
    }
}

0 赞同 0 条回复

阿尚普通 2023年7月18日下午8:36

//前序序列化
public class Codec {
    final String NULL = "#";
    final String SP = ",";

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return new String();
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null || data.length() == 0) return null;
        LinkedList<String> list = new LinkedList<>();
        for(String str : data.split(SP)){
            list.add(str);
        }
        return deserialize(list);
    }

    public void serialize(TreeNode root, StringBuilder sb) {
        if(root == null){
            sb.append(NULL);
            sb.append(SP);
            return;
        }

        sb.append(root.val);
        sb.append(SP);

        serialize(root.left, sb);
        serialize(root.right, sb);
    }

    public TreeNode deserialize(LinkedList<String> list) {
        if(list.size() == 0) return null;

        String val = list.removeFirst();
        if(NULL.equals(val)) return null;
        TreeNode root = new TreeNode(Integer.parseInt(val));

        root.left = deserialize(list);
        root.right = deserialize(list);

        return root;

    }
}

//后序序列化
public class Codec {
    final String NULL = "#";
    final String SP = ",";

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return new String();
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null || data.length() == 0) return null;
        LinkedList<String> list = new LinkedList<>();
        for(String str : data.split(SP)){
            list.add(str);
        }
        return deserialize(list);
    }

    public void serialize(TreeNode root, StringBuilder sb) {
        if(root == null){
            sb.append(NULL);
            sb.append(SP);
            return;
        }
        serialize(root.left, sb);
        serialize(root.right, sb);
        sb.append(root.val);
        sb.append(SP);
    }

    public TreeNode deserialize(LinkedList<String> list) {
        if(list.size() == 0) return null;

        String val = list.removeLast();
        if(NULL.equals(val)) return null;
        TreeNode root = new TreeNode(Integer.parseInt(val));

        root.right = deserialize(list);
        root.left = deserialize(list);

        return root;

    }
}

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月18日下午6:40

7.18
Day11：下面是代码
我的第二道困难题目…慢慢去看题解理解8成问题不大
但自己写时还是总是各种小问题不断，即使是简单题也一样
应该还是代码敲得太少了….希望我能多敲点代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.序列化
    public String serialize(TreeNode root) {
        if(root == null) return "[]";
        StringBuilder res = new StringBuilder("[");
        Queue<TreeNode> q = new LinkedList<>(); //注意是Queue<TreeNode>
        q.add(root);
        while(!q.isEmpty()){
            TreeNode node = q.poll();
            if(node != null){
                res.append(node.val).append(",");
                q.add(node.left);
                q.add(node.right);
            }
            else res.append("null,");
        }
        res.deleteCharAt(res.length() - 1);
        res.append("]");
        return res.toString();
    }

    // Decodes your encoded data to tree.反序列化
    public TreeNode deserialize(String data) {
        if(data.equals("[]")) return null;
        String[] vals = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        //字符串的第一个值为vals[0]，即root，之后从vals[1]取起
        int i = 1;
        while(!q.isEmpty()){
            TreeNode node = q.poll();
            if(!vals[i].equals("null")){
                node.left = new TreeNode(Integer.parseInt(vals[i]));
                q.add(node.left);
            }
            i++;
            if(!vals[i].equals("null")){
                node.right = new TreeNode(Integer.parseInt(vals[i]));
                q.add(node.right);
            }
            i++;
        }
        return root;
    }
}

0 赞同 0 条回复

AD钙奶普通 2023年7月18日下午5:41

采取先序遍历 + 递归的方式
StringBuilder 可变字符串，减少空间占用

public class Codec {
    int index = 0; // 全局索引
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        toStr(root,sb);
        return sb.toString();
    }

    public void toStr(TreeNode root, StringBuilder sb) {
        if(root == null) {
            sb.append("#,");
            return ;
        }
        sb.append(root.val).append(",");
        toStr(root.left,sb);
        toStr(root.right,sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        return toTree(data.split(","),index);
    }

    public TreeNode toTree(String[] nodes, int k) {
        if(index > nodes.length || "#".equals(nodes[index])) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(nodes[index]));
        root.left = toTree(nodes, index ++);
        root.right = toTree(nodes, index ++);
        return root;
    }
}

0 赞同 0 条回复

Luminous 普通 2023年7月18日下午5:06

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root==null) return "[]";
        StringBuilder res=new StringBuilder();
        res.append("[");
        Queue<TreeNode> q=new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            for(int i=q.size();i>0;i--){
                TreeNode node=q.poll();
                if(node!=null){
                    res.append(node.val+",");
                    q.add(node.left);
                    q.add(node.right);
                }else{
                    res.append("null,");
                }
            }
        }
        res.deleteCharAt(res.length()-1);
        res.append("]");
        return res.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.equals("[]")) return null;
        String[]vals=data.substring(1,data.length()-1).split(",");
        TreeNode root=new TreeNode(Integer.parseInt(vals[0]));
        Queue<TreeNode> q=new LinkedList<>();
        q.add(root);
        int i=1;
        while(!q.isEmpty()){
            for(int j=q.size();j>0;j--){
                TreeNode node=q.poll();
                if(!vals[i].equals("null")){
                    node.left=new TreeNode(Integer.parseInt(vals[i]));
                    q.add(node.left);
                }
                i++;
                 if(!vals[i].equals("null")){
                    node.right=new TreeNode(Integer.parseInt(vals[i]));
                    q.add(node.right);
                }
                i++;
            }
        }
        return root;
    } 
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

时间复杂度:O(n)
空间复杂度:O(n)

0 赞同 0 条回复

人生何处不青山普通 2023年7月18日下午5:01

今天刚好做到，利用前序遍历

function serialize(root: TreeNode | null): string {
    let resArr = [];
    const dfs = function (node: TreeNode | null) {
        if(!node) {
            resArr.push('null');
            return;
        }
        resArr.push(node.val);
        dfs(node.left);
        dfs(node.right);
    }
    dfs(root);
    return resArr.join(',');
};

/*
 * Decodes your encoded data to tree.
 */
function deserialize(data: string): TreeNode | null {
    const arr = data.split(',');
    const dfs = function() {
        let item = arr.shift();
        if(item === 'null') {
            return null;
        }
        let node = new TreeNode(parseInt(item));
        node.left = dfs();
        node.right = dfs();
        return node;
    }
    return dfs();
};

0 赞同 0 条回复

June 普通 2023年7月18日下午2:54

/** 使用前序遍历
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    List<String> list = new ArrayList<>();
    int index = 0;
    public String serialize(TreeNode root) {
        String ans = "";
        if (root == null)
            return ans;
        preOrderSer(root);
        ans = list.stream().collect(Collectors.joining(","));
        return ans;
    }

    public void preOrderSer(TreeNode node) {
        list.add(String.valueOf(node.val));
        if (node.left == null)
            list.add("x");
        else
            preOrderSer(node.left);
        if (node.right == null)
            list.add("x");
        else
            preOrderSer(node.right);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.length() == 0)
            return null;
        String[] array = data.split(",");
        return preOrderDes(array);
    }

    public TreeNode preOrderDes(String[] array) {
        if(array[index].equals("x"))
        {
            return null;
        }
        TreeNode node = new TreeNode(Integer.valueOf(array[index]));
        index++;
        node.left = preOrderDes(array);
        index++;
        node.right = preOrderDes(array);
        return node;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

0 赞同 0 条回复

NullPointerException 普通 2023年7月18日下午2:45

public class Codec {
public String serialize(TreeNode root) { //层序遍历去读，变成字符串，null也记录进去
if(root null) return “[]”;
StringBuilder res = new StringBuilder(“[“);
Queue queue = new LinkedList<>() {{ add(root); }};
while(!queue.isEmpty()) {
TreeNode node = queue.poll();
if(node != null) {
res.append(node.val + “,”);
queue.add(node.left);
queue.add(node.right);
}
else res.append(“null,”);
}
res.deleteCharAt(res.length() – 1);
res.append(“]”);
return res.toString();
}

public TreeNode deserialize(String data) {
    if(data.equals("[]")) return null;
    String[] vals = data.substring(1, data.length() - 1).split(",");
    TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
    Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
    int i = 1;
    while(!queue.isEmpty()) {
        TreeNode node = queue.poll();//层序遍历方式去填补子树 不为null就说明有节点
        if(!vals[i].equals("null")) {
            node.left = new TreeNode(Integer.parseInt(vals[i]));
            queue.add(node.left);
        }
        i++;
        if(!vals[i].equals("null")) {
            node.right = new TreeNode(Integer.parseInt(vals[i]));
            queue.add(node.right);
        }
        i++;
    }
    return root;
}

}

0 赞同 0 条回复

【二叉树专题】剑指 Offer 37. 序列化二叉树

共以下 24 个回答

# 回答此问题取消回复

【二叉树专题】剑指 Offer 37. 序列化二叉树

共以下 24 个回答

# 回答此问题 取消回复

# 回答此问题取消回复