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

Gg 普通 2023年3月29日下午8:50

public class Codec {

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

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

    }
}

0 赞同 0 条回复

lucca 普通 2023年1月7日下午3:09

BFS

时间复杂度 O(N)
空间复杂度 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> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node != null) {
                q.add(node.left);
                q.add(node.right);
                sb.append(node.val).append(',');
            } else sb.append("null,");
        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) return null;

        String[] s = data.split(",");
        int i = 1;
        TreeNode root = new TreeNode(Integer.parseInt(s[0]));
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (!"null".equals(s[i])) {
                TreeNode l = new TreeNode(Integer.parseInt(s[i]));
                node.left = l;
                q.add(l);
            }
            i++;
            if (!"null".equals(s[i])) {
                TreeNode r = new TreeNode(Integer.parseInt(s[i]));
                node.right = r;
                q.add(r);
            }
            i++;
        }
        return root;
    }
}

0 赞同 0 条回复

PatNick 普通 2022年12月26日下午6:07

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        queue = [root]
        ls = []
        while queue != []:
            cur = queue[0]
            if cur!= None and cur.left:
                queue.append(cur.left)
            if cur!= None and not cur.left:
                queue.append(None)
            if cur!= None and cur.right:
                queue.append(cur.right)
            if cur !=None and not cur.right:
                queue.append(None)

            if cur != None:
                ls.append(str(cur.val))
            else:
                ls.append("None")
            queue = queue[1:]
        st = ",".join(ls)
        return st

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        if data == "None":
            return None

        ls = data.split(",")
        root = TreeNode(int(ls[0]))
        queue = [root]
        i = 1
        while queue != []:
            cur = queue[0]
            # 建立左节点
            if ls[i] != "None":
                #  记得这里只能new 一个对象，同时用于建立子节点和list添加
                left = TreeNode(int(ls[i]))
                cur.left = left
                queue.append(left)

            i += 1
            # 建立右节点
            if ls[i] != "None":
                right = TreeNode(int(ls[i]))
                cur.right = right
                queue.append(right)
            i += 1
            queue = queue[1:]
        return root

0 赞同 0 条回复

派大星普通 2022年12月2日下午11:04

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 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) {

        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 条回复

symbol 普通 2022年11月23日下午9:32

class Codec:

    def serialize(self, root):
        if not root:
            return "#!"
        cur_str = str(root.val)+"!" # 得到当前层的字符串形式
        left_str = self.serialize(root.left) # 序列化左子树
        right_str = self.serialize(root.right) # 序列化右子树

        return cur_str + left_str + right_str # 将当前得到的字符串和左右子树的序列化结果返回
    def BuildTree(self, data):
        # 前序遍历 第一个数为根节点   
        val = data.pop(0) # pop()/pop(-1) 弹出第n个元素  pop(0)弹出第0个元素
        # 为 # 返回空节点
        if val == "#":
            return None
        node = TreeNode(int(val)) # 建立根节点
        node.left = self.BuildTree(data) # 建立左子树
        node.right = self.BuildTree(data) # 建立右子树

        return node
    def deserialize(self, data):
        data = data.split("!") # 将字符串分割成数组
        root = self.BuildTree(data) # 根据数组建立树

        return root

0 赞同 0 条回复

symbol 普通 2022年11月23日下午9:32

class Codec:

    def serialize(self, root):
        if not root:
            return "#!"
        cur_str = str(root.val)+"!" # 得到当前层的字符串形式
        left_str = self.serialize(root.left) # 序列化左子树
        right_str = self.serialize(root.right) # 序列化右子树

        return cur_str + left_str + right_str # 将当前得到的字符串和左右子树的序列化结果返回
    def BuildTree(self, data):
        # 前序遍历 第一个数为根节点   
        val = data.pop(0) # pop()/pop(-1) 弹出第n个元素  pop(0)弹出第0个元素
        # 为 # 返回空节点
        if val == "#":
            return None
        node = TreeNode(int(val)) # 建立根节点
        node.left = self.BuildTree(data) # 建立左子树
        node.right = self.BuildTree(data) # 建立右子树

        return node
    def deserialize(self, data):
        data = data.split("!") # 将字符串分割成数组
        root = self.BuildTree(data) # 根据数组建立树

        return root

0 赞同 0 条回复

lobort 普通 2022年11月22日上午12:23

public class Codec {
    //层序遍历来做
    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();
    }

    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;
    }
}

0 赞同 0 条回复

浅夏的无奈普通 2022年11月13日下午4:26

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 no = queue.poll();
            if(no != null){
                queue.add(no.left);
                queue.add(no.right);
                build.append(no.val+",");
            }else{
                build.append("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 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 条回复

yanshuojune 普通 2022年11月13日上午12:23

解题思路：使用层序遍历思想，序列化时，记录当前节点值，子节点为None时，也进行保存，反序列化时，将不为None得数构造成节点并放入队列，循环队列不为空的情况，弹出节点作为当前节点，下一个不为None的节点作为左节点，在下一个不为None的节点作为右节点。
时间复杂度：O（n）
空间复杂度：O(n)

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        import collections
        queue = collections.deque()
        queue.append(root)
        res = []
        if not root:
            return '[]'
        while queue:
            cur_node = queue.popleft()
            if cur_node:
                res.append(str(cur_node.val))
                queue.append(cur_node.left)
                queue.append(cur_node.right)
            else:
                res.append('None')
        return '[' + ' '.join(res) + ']'



    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        if data == '[]':
            return None
        vals = data[1:-1].split()
        queue = collections.deque()
        root = TreeNode(int(vals[0]))
        queue.append(root)
        i = 1
        while queue:
            cur_node = queue.popleft()
            if vals[i] != 'None':
                cur_node.left = TreeNode(int(vals[i]))
                queue.append(cur_node.left)
            i += 1
            if vals[i] != 'None':
                cur_node.right = TreeNode(int(vals[i]))
                queue.append(cur_node.right)
            i += 1
        return root

0 赞同 0 条回复

小肸永久会员 2022年11月11日下午4:35

思路：序列化成一个字符串，反序列化时要能够确定每一个节点的左右子节点。
实现方式一：层序遍历，BFS。序列化时需要遍历每一个节点，需要一个队列实现层序遍历。还要算上空节点。时间和空间复杂度都为O(N)，反序列化时的时间和空间复杂度也都为O(N)。

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();
            if (node != null) {
                queue.add(node.left);
                queue.add(node.right);
                res.append(node.val + " ");
            } else {
                res.append("null ");
            }
        }
        return res.toString();
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == "") {
            return null;
        }
        String[] nums = data.split(" ");
        // 构建根节点root
        TreeNode root = new TreeNode(Integer.valueOf(nums[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int i = 0;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            i ++;
            if (!nums[i].equals("null")) {
                TreeNode leftNode = new TreeNode(Integer.valueOf(nums[i]));
                queue.add(leftNode);
                node.left = leftNode;
            }
            i ++;
            if (!nums[i].equals("null")) {
                TreeNode rightNode = new TreeNode(Integer.valueOf(nums[i]));
                queue.add(rightNode);
                node.right = rightNode;
            }
        }
        return root;
    }
}

实现方式二：前序遍历，dfs。都会访问树中所有节点一次，递归会使用栈空间。所以序列化和反序列化的时间和空间的复杂度都为O(N)。

public class Codec {
    private int index = 0;
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        return serialize(root, new StringBuilder()).toString();
    }
    private StringBuilder serialize(TreeNode root, StringBuilder str) {
        if (root == null) {
            str.append("null ");
        } else {
            str.append(root.val + " ");
            serialize(root.left, str);
            serialize(root.right, str);
        }
        return str;
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] nums = data.split(" ");
        return deserialize(nums);
    }
    private TreeNode deserialize(String[] nums) {
        if (nums[index].equals("null")) {
            index ++;
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(nums[index]));
        index ++;
        root.left = deserialize(nums);
        root.right = deserialize(nums);
        return root;      
    }
}

0 赞同 0 条回复

波波_1936 普通 2022年11月10日下午10:16

    public class Codec {
        //时间复杂度O(n)
        //空间复杂度O(n)
        //dfs
        // 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[] array = data.split(",");
            List<String> list = new LinkedList<>(Arrays.asList(array));
            return rdeserialize(list);
        }

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

        private TreeNode rdeserialize(List<String> list) {
            if (list.get(0).equals("none")) {
                list.remove(0);
                return null;
            }
            TreeNode node = new TreeNode(Integer.valueOf(list.get(0)));
            list.remove(0);
            node.left = rdeserialize(list);
            node.right = rdeserialize(list);
            return node;
        }
    }

0 赞同 0 条回复

黎昕普通 2022年11月9日下午8:43

垃圾解法：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        queue1=collections.deque()
        queue2=collections.deque()
        if root:
            queue1.append(root)
        else:
            return
        while queue1:
            node=queue1.popleft()
            if node:
                queue1.append(node.left)
                queue1.append(node.right)
            queue2.append(node)
        return queue2   # 按理来说，这里应当是返回一个str类型且末尾的none是需要去掉的，但是这里取巧了



    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str # 因为是自己调用的，所以这里直接上一步用的deque的返回值，这里使用的是deque作为传入的参数
        :rtype: TreeNode
        """

        # 思路：采用一个递归的方式，已经通过数学方式推导知道了在序列化的这种情况下parent节点与左右孩子节点的index关系
        # 设 parent在data中的index是 n，设前面含有m个none节点，则在起始index为0的情况下，左孩子的index是 2(n-m)+1，右孩子的index是 2(n-m)+2
        # 序列data作为外部变量直接调用，，现在的问题是，难道每个节点都要遍历一次前面有多少个none吗？我们应该在外部遍历一遍，把这个信息整体存下来
        if not data:
            return
        num=0
        numOfNone=[]
        for x in data:
            if not x:
                num+=1
            numOfNone.append(num) # 用于存储每个节点下标前面有多少个none在queue/data中
        length=len(data)-1

        def dfs(i):
            nonlocal data,numOfNone
            if i>length or (not data[i]):
                return
            root=TreeNode(data[i].val)
            root.left=dfs(2*(i-numOfNone[i])+1)
            root.right=dfs(2*(i-numOfNone[i])+2)
            return root
        return dfs(0)



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

大神解法手动狗头

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        return root


    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        return data


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

0 赞同 0 条回复

马啸天永久会员 2022年11月7日下午3:16

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) {

        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 条回复

just 普通 2022年11月6日下午3:05

//层序遍历
/**
* 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;
    res+='[';
    if(!root){
        res+=']';
        return res;
    }
    queue<TreeNode*> que;
    que.push(root);
    while(!que.empty()){
        TreeNode* cur=que.front();
        que.pop();
        if(cur==nullptr){
            res+="null,";
        }
        else {
            res+=to_string(cur->val);
            res+=',';
            que.push(cur->left);
            que.push(cur->right);
        }
    }
    res.pop_back();
    res+=']';
    return res;

}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
    if(data=="[]") return nullptr;
    data.erase(data.begin());
    data.back()=',';
    vector<string> datum;
    //datum.push_back(0);
    int start=0;
    for(int i=0;i<data.size();++i){

        if(data[i]==','){
            string str=data.substr(start,i-start);
            datum.push_back(str);
            start=i+1;
        }
    }
    if(datum[0]=="null") return nullptr;
    TreeNode* root=new TreeNode(stoi(datum[0]));
    int pos=1;
    queue<TreeNode*> que;
    que.push(root);
    while(!que.empty()&&pos<datum.size()){
        TreeNode* cur=que.front();
        que.pop();
        if(datum[pos]!="null"){
            TreeNode* newnode=new TreeNode(stoi(datum[pos]));
            cur->left=newnode;
            que.push(newnode);
        }
        pos++;
        if(datum[pos]!="null"){
            TreeNode* newnode=new TreeNode(stoi(datum[pos]));
            cur->right=newnode;
            que.push(newnode);
        }
        pos++;
    }
    return root;



}

};

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

0 赞同 0 条回复

你有点可爱喔普通 2022年11月4日下午7:39

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

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            // //
            // this.root = root;
            // return null;
            if (root == null) {
                return null;
            }
            StringBuilder sb = 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);
                    sb.append(t.val + ",");
                } else {
                    sb.append("null,");
                }
            }
            return sb.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<>();
            queue.add(root);
            int i = 1;
            while (!queue.isEmpty()) {
                TreeNode t = queue.poll();
                if (!s[i].equals("null")) {
                    TreeNode t1 = new TreeNode(Integer.parseInt(s[i]));
                    t1.left = t1;
                    queue.add(t1);
                }
                i++;
                if (!s[i].equals("null")) {
                    TreeNode t1 = new TreeNode(Integer.parseInt(s[i]));
                    t1.right = t1;
                    queue.add(t1);
                }
                i++;
            }
            return root;
        }
    }

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

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月4日下午3:23

时间空间复杂度都为O（n）

/**
 * 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 "";
        Queue<TreeNode> queue = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        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()==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 t1 = new TreeNode(Integer.parseInt(s[i]));
                t.left = t1;
                queue.add(t1);
            }
            i++;
            if(!s[i].equals("null")){
                TreeNode t1 = new TreeNode(Integer.parseInt(s[i]));
                t.right = t1;
                queue.add(t1);
            }
            i++;
        }
        return root;
    }
}

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

0 赞同 0 条回复

Whatever 永久会员 2022年11月3日下午4:15

前序遍历，时间O(n)，空间O(n)

public class Codec {
    String sep = ",";
    String n = "NUll";
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serialize(root,sb);
        return sb.toString();
    }
    public void serialize(TreeNode root, StringBuilder sb){
        if(root == null){
            sb.append(n).append(sep);
            return;
        }
        sb.append(root.val).append(sep);
        serialize(root.left,sb);
        serialize(root.right,sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        LinkedList<String> nodes = new LinkedList<>();
        for(String s : data.split(sep)){
            nodes.addLast(s);
        }
        return deserialize(nodes);
    }
    public TreeNode deserialize(LinkedList<String> nodes){
        if(nodes.isEmpty()){
            return null;
        }
        String cur = nodes.removeFirst();
        if(cur.equals(n)){
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(cur));
        root.left = deserialize(nodes);
        root.right = deserialize(nodes);
        return root;
    }
}

0 赞同 0 条回复

T 普通 2022年11月3日下午3:24

根据层序遍历顺序打印

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<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(node != null) {
                sb.append(node.val).append(",");
                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.equals("[]")) return null;
        String[] nodes = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int i = 1;
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(!nodes[i].equals("null")) {
                node.left = new TreeNode(Integer.parseInt(nodes[i]));
                queue.add(node.left);
            }
            i++;
            if(!nodes[i].equals("null")) {
                node.right = new TreeNode(Integer.parseInt(nodes[i]));
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }
}

0 赞同 0 条回复

是梦终空永久会员 2022年11月3日下午12:06

时间O(n)
空间O(n)

public class Codec {
    //前序遍历,
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null)    return "";  //如果为空，返回空字符串
        StringBuilder str = new StringBuilder();
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);                  //添加头结点
        while(!que.isEmpty()){          
            TreeNode pre = que.poll();
            if(pre != null){            //如果pre不为空，就把左右节点加入队列，并且拼接val值 还有","
                que.add(pre.left);
                que.add(pre.right);;
                str.append(pre.val+",");
            }else{
                str.append("null"+","); //如果pre为空，就拼接null,
            }
        }
        return str.toString();          //返回str
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null || data.length() <= 0)  return null;        //为空返回Null
        String[] str = data.split(",");                             //把字符串通过","分隔开 存入数组
        Queue<TreeNode> que = new LinkedList<>();
        TreeNode root =new TreeNode(Integer.parseInt(str[0]));//头结点 
        que.add(root);
        int i = 1;                                                 //定义指针i
        while(!que.isEmpty()){
            TreeNode pre = que.poll();                             //出队列
            if(!str[i].equals("null")){                                 //如果数组第i个值不为空，就新建TreeNode节点，并作为pre节点的左子树。并入队。如果为空，就默认是null
                TreeNode left = new TreeNode(Integer.parseInt(str[i]));
                pre.left = left;
                que.add(pre.left);
            }
            i++;                                                    //每次判断完数组的一个值，指针++
            if(!str[i].equals("null")){
                TreeNode right = new TreeNode(Integer.parseInt(str[i]));//如果数组第i个值不为空，就新建TreeNode节点，并作为pre节点的右子树。并入队。如果为空，就默认是null
                pre.right = right;
                que.add(pre.right);
            }
            i++;
        }
        return root;
    }
}

0 赞同 0 条回复

追普通 2022年11月3日上午11:24

class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        //层序遍历将树化为力扣格式的字符串
        string s="[";
        if(root){//当树非空时
            queue<TreeNode*> que;
            TreeNode* tmp;
            que.emplace(root);
            while(!que.empty()){
                    tmp=que.front();
                    que.pop();
                    if(tmp){//如果队列当前节点非空，将该结点的值加入字符串并把左右结点放入队列
                        s+=to_string(tmp->val);
                        s+=",";
                        que.emplace(tmp->left);
                        que.emplace(tmp->right);
                    }
                    else{//当前结点为空，只需在字符串中加入"null,"即可
                        s+="null,";
                    }
            }
            //由于每个节点值后都加了“，”,最后会多一个“，”,删去它
            s.erase(s.length()-1,1);
            //保证和力扣格式一样，删去字符串最后多余的"null"
            while(s.rfind(",")!=string::npos){
                int index=s.rfind(",");
                if(s.substr(index)==",null"){
                    s.erase(index);
                }
                else break;
            }
        }
        s+="]";
        return s;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data=="[]") 
            return nullptr;
        //先处理字符串，把每个数字构造成节点放入数组中
        vector<TreeNode*> que;
        data.erase(0,1);
        while(data.find(",")!=string::npos){
            int idx=data.find(",");
            string snum=data.substr(0,idx);
            if(snum=="null"){//为空时直接把空指针放入数组
                que.emplace_back(nullptr);
            }
            else{//如果非空（为数字），构造成节点放入数组中
                int num=stoint(snum);
                TreeNode* node=new TreeNode(num);
                que.emplace_back(node);
            }
            data.erase(0,idx+1);
        }
        //处理最后一个数字
        string snum=data.substr(0,data.length()-1);
        int num=stoint(snum);
        TreeNode* node=new TreeNode(num);
        que.emplace_back(node);
        //根结点为数组第一个
        TreeNode* root=que[0];
        int size=que.size();
        //构造队列，类似层序遍历
        queue<TreeNode*> q;
        q.emplace(root);
        int i=1;//i用来遍历数组
        while(!q.empty()){
            TreeNode* tmp=q.front();
            q.pop();
            if(i<size&&que[i]){
                q.emplace(que[i]);
                tmp->left=que[i];
            }
            i++;
            if(i<size&&que[i]){
                q.emplace(que[i]);
                tmp->right=que[i];
            }
            i++;
        }
        return root;
    }
    int stoint(string s){//字符串转数字函数（考虑负数情况）
        int sum=0;
        if(s[0]=='-'){
            for(int i=1;i<s.length();i++)
                sum=sum*10+s[i]-'0';
            sum*=-1;
        }
        else 
            for(int i=0;i<s.length();i++)
                sum=sum*10+s[i]-'0';
        return sum;
    }
};

使用层序遍历进行序列化，注意需要对最后的几个null进行处理使输出符合该题的输出规范

0 赞同 0 条回复

So 普通 2022年11月2日下午11:37

/**
 * 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 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) {
        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));

时间：O(n)，空间：O(n)

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月2日下午11:08

自己写了一遍，没有通过主要问题如下

第一个错误在生成字符串时，最开始用的层次遍历，判断条件是节点为空不加入，向sb中append“#”，事实证明有问题，因为这样会丢失空子树的null值
第二个错误是最后采用的是toCharArray的方式变成char数组，忽略了负数的可能性，所以出错

/**
使用#代替null，当遇到#说明此处无节点
 */
public class Codec {
    //[1,2,3,null,null,4,5];
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if(root == null) return "";
        LinkedList<TreeNode> queue = new LinkedList<>(); 
        queue.push(root);
        while(!queue.isEmpty()){
                TreeNode cur = queue.removeFirst();
               if(cur != null){
                   queue.addLast(cur.left);
                   queue.addLast(cur.right);
                   sb.append(cur.val);
               }else{
                   sb.append("#");
               }

        }
        //此时得到的是123##45##;需要去除最后的##，长度为1+2+3+4..(height+1)*height/2
        // return sb.substring(0,(height+1)*height/2+1).toString();
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null || data.length() <= 0) return null;
        //得到123##45
        char[] c = data.toCharArray();
        LinkedList<TreeNode> queue = new LinkedList<>(); 
        TreeNode root = new TreeNode(c[0]-'0');
        TreeNode tmp = root;
        queue.addLast(tmp);
        int i = 1;
        while(!queue.isEmpty()){
            TreeNode cur = queue.removeFirst();
            if(c[i] != '#'){
                TreeNode left = new TreeNode(c[i]-'0');
                cur.left = left;
                queue.addLast(left);
            }
            i++;
            if(c[i]!= '#'){
                TreeNode right = new TreeNode(c[i]-'0');
                cur.right = right;
                queue.addLast(right);
            }
            i++;
        }
        return root;
    }
}

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

改后->判断单位为String，避免正负号的问题。使用split

序列化时间复杂度O(N) 空间复杂度O(N)

反序列化时间复杂度O(N) 空间复杂度O(N)

/**
使用#代替null，当遇到#说明此处无节点
 */
public class Codec {
    //[1,2,3,null,null,4,5];
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if(root == null) return "";
        LinkedList<TreeNode> queue = new LinkedList<>(); 
        queue.push(root);
        while(!queue.isEmpty()){
                TreeNode cur = queue.removeFirst();
               if(cur != null){
                   queue.addLast(cur.left);
                   queue.addLast(cur.right);
                   sb.append(cur.val+",");
               }else{
                   sb.append("#,");
               }

        }
        //此时得到的是123##45##;需要去除最后的##，长度为1+2+3+4..(height+1)*height/2
        // return sb.substring(0,(height+1)*height/2+1).toString();
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null || data.length() <= 0) return null;
        //得到123##45
        String[] c = data.split(",");
        LinkedList<TreeNode> queue = new LinkedList<>(); 
        TreeNode root = new TreeNode(Integer.parseInt(c[0]));
        TreeNode tmp = root;
        queue.addLast(tmp);
        int i = 1;
        while(!queue.isEmpty()){
            TreeNode cur = queue.removeFirst();
            if(!c[i].equals("#")){
                TreeNode left = new TreeNode(Integer.parseInt(c[i]));
                cur.left = left;
                queue.addLast(left);
            }
            i++;
            if(!c[i].equals("#")){
                TreeNode right = new TreeNode(Integer.parseInt(c[i]));
                cur.right = right;
                queue.addLast(right);
            }
            i++;
        }
        return root;
    }
}

0 赞同 0 条回复

易水寒永久会员 2022年11月2日下午10:52

前序

public class Codec {
    String SEP = ",";
    String NULL = "#";
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        build(root, sb);
        return sb.toString();
    }

    private void build(TreeNode root, StringBuilder sb) {
        if(root == null) {
            sb.append(NULL).append(SEP);
            return;
        }
        sb.append(root.val).append(SEP);
        build(root.left, sb);
        build(root.right, sb);
    }


    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        LinkedList<String> ls = new LinkedList<>();
        for(String string : data.split(SEP)) {
            ls.add(string);
        }
        return deserialize(ls);
    }
    private TreeNode deserialize(LinkedList<String> ls) {
        String fst = ls.removeFirst();
        if(fst.equals(NULL)) {
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(fst));
        node.left = deserialize(ls);
        node.right = deserialize(ls);
        return node;
    }
}

0 赞同 0 条回复

天然普通 2022年11月2日下午10:47

第一个想法比较暴力，是用模版遍历前序和中序，然后在反序列化函数中，分割出来前序数组和中序数组，用前几天出的前序和中序题的模版合成链表的方法。
然后是题解的解法，用层次遍历，刚开始我用层次处理不了有子节点为None的情况，然后题解使用if去判断解决这个问题，反序列化和序列化算法差不多，无非是res存储的不同。时间复杂度O(n），空间复杂度O(n)

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        if not root : return root
        res,num= [],[root]
        while num:
            k = num.pop(0)
            if k:
                res.append(str(k.val)+",")
                num.append(k.left) 
                num.append(k.right)
            else:
                res.append("n,")
        return ''.join(res)

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        if not data:return []
        res = data.split(",")
        root = TreeNode(res[0])
        num ,i= [root],1
        while num:

            k = num.pop(0)
            if res[i]!= "n":
                k.left = TreeNode(res[i])
                num.append(k.left)
            i+=1

            if res[i] != "n":
                k.right = TreeNode(res[i])
                num.append(k.right)
            i+=1

        return root

0 赞同 1 条回复

@ 普通 @ 天然 2022年11月8日下午9:31

第一个想法行不通，因为前几天做的那些是没有重复元素的，这道题的测试用例有重复数据的。

登录以回复

青木普通 2022年11月2日下午10:45

/**
    层序遍历就行，保存成str后，用一个指针指向当前节点的孩子节点，然后继续层序遍历就好了
    用StringBuilder 比单纯用String 快好多

    时间复杂度O(n)
    空间复杂度O(n)
 */
public class Codec {

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

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == "") return null;
        String[] s = data.split(",");
        int i = 0, n = s.length;

        Queue<TreeNode> q = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(s[0]));
        TreeNode node = new TreeNode();
        q.offer(root);
        while(i<n-1){
            node = q.poll();
            if(!"null".equals(s[++i])){
                node.left = new TreeNode(Integer.parseInt(s[i]));
                q.offer(node.left);
                // cnt+=1;
            }
            if(!"null".equals(s[++i])){
                node.right = new TreeNode(Integer.parseInt(s[i]));
                q.offer(node.right);
                // cnt+=1
            }
        }

        return root;
    }
}

0 赞同 0 条回复

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

共以下 25 个回答

BFS

# 回答此问题取消回复

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

共以下 25 个回答

BFS

# 回答此问题 取消回复

# 回答此问题取消回复