449.序列化和反序列化二叉搜索树

链接：449.序列化和反序列化二叉搜索树
难度：Medium
标签：树、深度优先搜索、广度优先搜索、设计、二叉搜索树、字符串、二叉树
简介：给你一棵二叉树，它的根为 root 。请你删除 1 条边，使二叉树分裂成两棵子树，且它们子树和的乘积尽可能大。 。

题解 1 - typescript

• 编辑时间：2021-08-14
• 执行用时：108ms
• 内存消耗：46.1MB
• 编程语言：typescript
• 解法介绍：JSON 序列化。

function serialize(root: TreeNode | null): string {
  return JSON.stringify(root);
}
function deserialize(data: string): TreeNode | null {
  return JSON.parse(data);
}

题解 2 - cpp

• 编辑时间：2022-05-11
• 执行用时：64ms
• 内存消耗：45.7MB
• 编程语言：cpp
• 解法介绍：递归。

class Codec {
   public:
    string serialize(TreeNode *root) {
        if (root == nullptr) return "(-1)";
        return "(" + to_string(root->val) + "," + serialize(root->left) + "," +
               serialize(root->right) + ")";
    }
    TreeNode *deserialize(string data) {
        if (data == "(-1)") return nullptr;
        string l, r;
        int val = analysis(data, l, r);
        TreeNode *ans = new TreeNode(val);
        ans->left = deserialize(l);
        ans->right = deserialize(r);
        return ans;
    }
    int analysis(string &data, string &l, string &r) {
        int level = 0, n = data.size(), val;
        int i = 0, prev = 1, cnt = 0;
        for (; i < n; i++) {
            int ch = data[i];
            if (ch == '(') {
                level++;
            } else if (ch == ')') {
                level--;
            } else if (ch == ',' && level == 1) {
                string substr = data.substr(prev, i - prev);
                if (cnt == 0)
                    val = stoi(substr);
                else if (cnt == 1)
                    l = substr;
                cnt++;
                prev = i + 1;
            }
        }
        r = data.substr(prev, i - prev - 1);
        return val;
    }
};

题解 3 - python

• 编辑时间：2023-09-04
• 执行用时：248ms
• 内存消耗：19.74MB
• 编程语言：python
• 解法介绍：同上。

class Codec:
    def serialize(self, node: Optional[TreeNode]) -> str:
        """Encodes a tree to a single string.
        """
        if not node:
            return "N"
        return f"{node.val},({self.serialize(node.left)}),({self.serialize(node.right)})"
    def deserialize(self, s: str) -> Optional[TreeNode]:
        """Decodes your encoded data to tree.
        """
        if s == "N":
            return None
        s1 = s2 = s3 = ''
        split_idx = -1
        level = 0
        for i in range(len(s)):
            if s[i] == '(':
                level += 1
            elif s[i] == ')':
                level -= 1
            elif s[i] == ',' and level == 0:
                if split_idx == -1:
                    s1 = s[:i]
                    split_idx = i + 1
                else:
                    s2 = s[split_idx + 1:i - 1]
                    s3 = s[i + 2:-1]
        return TreeNode(int(s1), self.deserialize(s2), self.deserialize(s3))

题解 4 - python

• 编辑时间：2023-09-04
• 执行用时：248ms
• 内存消耗：19.74MB
• 编程语言：python
• 解法介绍：同上。

class Codec:
    def serialize(self, node: Optional[TreeNode]) -> str:
        """Encodes a tree to a single string.
        """
        if not node:
            return "N"
        return f"{node.val},({self.serialize(node.left)}),({self.serialize(node.right)})"
    def deserialize(self, s: str) -> Optional[TreeNode]:
        """Decodes your encoded data to tree.
        """
        if s == "N":
            return None
        s1 = s2 = s3 = ''
        split_idx = -1
        level = 0
        for i in range(len(s)):
            if s[i] == '(':
                level += 1
            elif s[i] == ')':
                level -= 1
            elif s[i] == ',' and level == 0:
                if split_idx == -1:
                    s1 = s[:i]
                    split_idx = i + 1
                else:
                    s2 = s[split_idx + 1:i - 1]
                    s3 = s[i + 2:-1]
        return TreeNode(int(s1), self.deserialize(s2), self.deserialize(s3))

题解 5 - python

• 编辑时间：2023-09-04
• 执行用时：248ms
• 内存消耗：19.74MB
• 编程语言：python
• 解法介绍：同上。

class Codec:
    def serialize(self, node: Optional[TreeNode]) -> str:
        """Encodes a tree to a single string.
        """
        if not node:
            return "N"
        return f"{node.val},({self.serialize(node.left)}),({self.serialize(node.right)})"
    def deserialize(self, s: str) -> Optional[TreeNode]:
        """Decodes your encoded data to tree.
        """
        if s == "N":
            return None
        s1 = s2 = s3 = ''
        split_idx = -1
        level = 0
        for i in range(len(s)):
            if s[i] == '(':
                level += 1
            elif s[i] == ')':
                level -= 1
            elif s[i] == ',' and level == 0:
                if split_idx == -1:
                    s1 = s[:i]
                    split_idx = i + 1
                else:
                    s2 = s[split_idx + 1:i - 1]
                    s3 = s[i + 2:-1]
        return TreeNode(int(s1), self.deserialize(s2), self.deserialize(s3))

题解 6 - python

• 编辑时间：2023-09-04
• 执行用时：248ms
• 内存消耗：19.74MB
• 编程语言：python
• 解法介绍：同上。

class Codec:
    def serialize(self, node: Optional[TreeNode]) -> str:
        """Encodes a tree to a single string.
        """
        if not node:
            return "N"
        return f"{node.val},({self.serialize(node.left)}),({self.serialize(node.right)})"
    def deserialize(self, s: str) -> Optional[TreeNode]:
        """Decodes your encoded data to tree.
        """
        if s == "N":
            return None
        s1 = s2 = s3 = ''
        split_idx = -1
        level = 0
        for i in range(len(s)):
            if s[i] == '(':
                level += 1
            elif s[i] == ')':
                level -= 1
            elif s[i] == ',' and level == 0:
                if split_idx == -1:
                    s1 = s[:i]
                    split_idx = i + 1
                else:
                    s2 = s[split_idx + 1:i - 1]
                    s3 = s[i + 2:-1]
        return TreeNode(int(s1), self.deserialize(s2), self.deserialize(s3))

题解 7 - python

• 编辑时间：2023-09-04
• 执行用时：248ms
• 内存消耗：19.74MB
• 编程语言：python
• 解法介绍：同上。

class Codec:
    def serialize(self, node: Optional[TreeNode]) -> str:
        """Encodes a tree to a single string.
        """
        if not node:
            return "N"
        return f"{node.val},({self.serialize(node.left)}),({self.serialize(node.right)})"
    def deserialize(self, s: str) -> Optional[TreeNode]:
        """Decodes your encoded data to tree.
        """
        if s == "N":
            return None
        s1 = s2 = s3 = ''
        split_idx = -1
        level = 0
        for i in range(len(s)):
            if s[i] == '(':
                level += 1
            elif s[i] == ')':
                level -= 1
            elif s[i] == ',' and level == 0:
                if split_idx == -1:
                    s1 = s[:i]
                    split_idx = i + 1
                else:
                    s2 = s[split_idx + 1:i - 1]
                    s3 = s[i + 2:-1]
        return TreeNode(int(s1), self.deserialize(s2), self.deserialize(s3))