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

小肸永久会员 2023年8月31日下午5:10

public class Codec {
    //前序遍历进行dfs序列化，后序变量和层次遍历都可以序列化和反序列化，因为可以确认根节点的位置
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        return dfsSerialize(root, new StringBuilder("")).toString();
    }
    private StringBuilder dfsSerialize(TreeNode node, StringBuilder res) {
        if (node == null) {
            res.append("null,");
        } else {
            res.append(node.val + ",");
            dfsSerialize(node.left, res);
            dfsSerialize(node.right, res);
        }
        return res;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] strings = data.split(",");
        List<String> strList = new LinkedList<>(Arrays.asList(strings));
        return dfsDeserialize(strList);        
    }
    private TreeNode dfsDeserialize(List<String> strList) {
        if ("null".equals(strList.get(0))) {
            strList.remove(0);
            return null;
        }
        TreeNode node = new TreeNode(Integer.valueOf(strList.remove(0)));
        node.left = dfsDeserialize(strList);
        node.right = dfsDeserialize(strList);
        return node;
    }
}

0 赞同 0 条回复

sc_Yang 普通 2023年8月31日上午8:28

先序深度优先遍历序列化

/**
 * 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.
    // 利用先序深度遍历 + 树的边界为none，来唯一序列化
    void rserialize(TreeNode* root, string& str){
        if(root==NULL){
            str += "None,";
        }else{
            str += to_string(root->val)+",";
            rserialize(root->left, str);
            rserialize(root->left, str);
        }
    }
    string serialize(TreeNode* root) {
        string result;
        rserialize(root, result);
        return result;
    }

    // Decodes your encoded data to tree.
    TreeNode* rdeserialize(list<string>& dataArray){
        if(dataArray.front()=="None"){
            dataArray.erase(dataArray.begin());
            return
        }
        TreeNode* root = new TreeNode(stoi(dataArray.front()));
        dataArray.erase(dataArray.front());
        root->left = rdeserialize(dataArray);
        root->right = rdeserialize(dataArray);
        return root;
    }
    TreeNode* deserialize(string data) {
        list<string> dataArray;
        string tmpstr;
        // 将原字符串拆分并输入至dataArray中
        for(auto& ch : data){
            if(ch==','){
                dataArray.push_back(tmpstr);
                tmpstr.clear();
            }else{
                tmpstr.push_back(ch);
            }
        }
        if(!tmpstr.empty()){ // 最后一个字符串添加进list中
            dataArray.push_back(tmpstr);
            str.clear();
        }
        // 该处其实就是核心执行递归解码
        return rdeserialize(dataArray);
    }
};

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

0 赞同 0 条回复

sincere 普通 2023年8月30日下午10:55

思路：前中后序都无法唯一确定二叉树，结合题意需要用层序遍历进行序列化，反序列化时由于不存在的子节点是null，所以这是一个完全二叉树，按照顺序构建即可
复杂度：完全遍历了一遍，都存了，所以时间复杂度、空间复杂度都是O(n)

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);

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

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

0 赞同 0 条回复

c 普通 2023年8月23日下午9:31

层序遍历保存，再按顺序构建

public class Codec {

    public String serialize(TreeNode root) {
        if (root==null){
            return "";
        }
        String res = "";
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node=queue.poll();
                if(node==null){
                    res=res+"Null,";
                }else{
                    res=res+String.valueOf(node.val)+",";
                    if (node.left!=null){
                        queue.add(node.left);
                    }else {
                        queue.add(null);
                    }
                    if (node.right!=null){
                        queue.add(node.right);
                    }else {
                        queue.add(null);
                    }
                }
            }
        }
        return res.substring(0,res.length()-1);
    }

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

    }
}

0 赞同 0 条回复

JustRtn 普通 2023年8月23日下午9:28

按层次遍历以存储val为字符串，val之间使用逗号分隔；
通过stringstreamp配合getline函数分割字符串，使用队列存储当前需要建立左右子树的节点

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (root == nullptr) {
            return "";
        }
        std::string str;
        std::queue<TreeNode*> que;
        que.push(root);
        while (!que.empty()) {
            auto* node = que.front();
            que.pop();

            if (node != nullptr) {
                str.append(std::to_string(node->val));
                que.push(node->left);
                que.push(node->right);
            } else {
                if (que.empty()) {
                    break;
                }
                str.append("null");
            }
            str.append(",");
        }

        return str;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.empty()) {
            return nullptr;
        }
        std::stringstream stm(data);
        std::string s;
        std::queue<TreeNode*> que;

        TreeNode* root;
        if (getline(stm, s, ',')) {
            root = new TreeNode(stoi(s));
            que.push(root);
        }

        while (!que.empty()) {
            TreeNode* node = que.front();
            que.pop();

            if (getline(stm, s, ',') && s != "null") {
                TreeNode* left = new TreeNode(stoi(s));
                que.push(left);
                node->left = left;
            }

            if (getline(stm, s, ',') && s != "null") {
                TreeNode* right = new TreeNode(stoi(s));
                que.push(right);
                node->right = right;
            }

        }
        return root;
    }
};

0 赞同 0 条回复

塔底的仰望永久会员 2023年8月23日下午4:23

层序遍历编码，解码的时候，使用一个辅助队列来存储非null节点。依次赋值队首元素的左右孩子

public class Codec {

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

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] strArray = data.split(",");
        if (strArray.length <= 2) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(strArray[1]));
        TreeNode p = null;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int sum = -1;
        for (int i = 2; i < strArray.length; i++) {
            if (sum == -1) {
                p = queue.poll();
                sum = 1;
            }
            TreeNode temp = null;
            if (!strArray[i].equals("null")) {
                temp = new TreeNode(Integer.parseInt(strArray[i]));
                queue.add(temp);
            }
            if (sum == 1) {
                p.left = temp;
            } else {
                p.right = temp;
            }
            sum--;
        }
        return root;
    }
}

0 赞同 0 条回复

别扒拉我普通 2023年8月23日下午4:02

层次遍历

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null){
            return "[]";
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        StringBuilder res = new StringBuilder("[");
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node != null){
                res.append(node.val + ",");
                queue.offer(node.left);
                queue.offer(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<>();
        queue.offer(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.offer(node.left);
            }
            i++;
            if(!vals[i].equals("null")){
                node.right = new TreeNode(Integer.parseInt(vals[i]));
                queue.offer(node.right);
            }
            i++;
        }
        return root;
    }
}

0 赞同 0 条回复

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

共以下 7 个回答

# 回答此问题取消回复

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

共以下 7 个回答

# 回答此问题 取消回复

# 回答此问题取消回复