LeetCode|LeetCode #449 Serialize and Deserialize BST 序列化和反序列化二叉搜索树 LeetCode#449SerializeandDeserializeB

449 Serialize and Deserialize BST 序列化和反序列化二叉搜索树 Description:
Serialization is converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure.
The encoded string should be as compact as possible.
Example:
Example 1:
Input: root = [2,1,3]
Output: [2,1,3]
Example 2:
Input: root = []
Output: []
Constraints:
The number of nodes in the tree is in the range [0, 10^4].
0 <= Node.val <= 10^4
The input tree is guaranteed to be a binary search tree.
题目描述:
序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。
设计一个算法来序列化和反序列化二叉搜索树。对序列化/反序列化算法的工作方式没有限制。您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。
编码的字符串应尽可能紧凑。
示例 :
示例 1：
输入：root = [2,1,3]
输出：[2,1,3]
示例 2：
输入：root = []
输出：[]
提示：
树中节点数范围是 [0, 10^4]
0 <= Node.val <= 10^4
题目数据保证输入的树是一棵二叉搜索树。
【LeetCode|LeetCode #449 Serialize and Deserialize BST 序列化和反序列化二叉搜索树】注意：
不要使用类成员/全局/静态变量来存储状态。你的序列化和反序列化算法应该是无状态的。
思路:
序列化采用后序遍历, 这样反序列化时可以直接从列表的最后拿不需要记录节点下标
时间复杂度O(n), 空间复杂度O(n)
代码:
C++:

/** * 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 { private: void post_order(TreeNode *root, string &result) { if (!root) return; post_order(root -> left, result); post_order(root -> right, result); result += to_string(root -> val) + " "; }TreeNode* helper(int lower, int upper, vector &nums) { if (nums.empty()) return nullptr; int val = nums.back(); if (val < lower or val > upper) return nullptr; nums.pop_back(); TreeNode *root = new TreeNode(val); root -> right = helper(val, upper, nums); root -> left = helper(lower, val, nums); return root; } public:// Encodes a tree to a single string. string serialize(TreeNode* root) { string result; post_order(root, result); return result; }// Decodes your encoded data to tree. TreeNode* deserialize(string data) { if (data.empty()) return nullptr; stringstream ss; string num; vector nums; ss << data; while (ss >> num) nums.emplace_back(stoi(num)); return helper(INT_MIN, INT_MAX, nums); } }; // Your Codec object will be instantiated and called as such: // Codec* ser = new Codec(); // Codec* deser = new Codec(); // string tree = ser->serialize(root); // TreeNode* ans = deser->deserialize(tree); // return ans;

Java:

/** * Definition for a binary tree node. * public class TreeNode { *int val; *TreeNode left; *TreeNode right; *TreeNode(int x) { val = x; } * } */ public class Codec { private StringBuilder postorder(TreeNode root, StringBuilder sb) { if (root == null) return sb; postorder(root.left, sb); postorder(root.right, sb); sb.append(root.val); sb.append(' '); return sb; }// Encodes a tree to a single string. public String serialize(TreeNode root) { StringBuilder sb = postorder(root, new StringBuilder()); if (sb.length() > 0) sb.deleteCharAt(sb.length() - 1); return sb.toString(); }public TreeNode helper(Integer lower, Integer upper, ArrayDeque nums) { if (nums.isEmpty()) return null; int val = nums.getLast(); if (val < lower || val > upper) return null; nums.removeLast(); TreeNode root = new TreeNode(val); root.right = helper(val, upper, nums); root.left = helper(lower, val, nums); return root; }// Decodes your encoded data to tree. public TreeNode deserialize(String data) { if (data.isEmpty()) return null; ArrayDeque nums = new ArrayDeque(); for (String s : data.split("\\s+")) nums.add(Integer.valueOf(s)); return helper(Integer.MIN_VALUE, Integer.MAX_VALUE, nums); } }// Your Codec object will be instantiated and called as such: // Codec ser = new Codec(); // Codec deser = new Codec(); // String tree = ser.serialize(root); // TreeNode ans = deser.deserialize(tree); // return ans;

Python:

# Definition for a binary tree node. # class TreeNode: #def __init__(self, x): #self.val = x #self.left = None #self.right = Noneclass Codec:def serialize(self, root: TreeNode) -> str: """Encodes a tree to a single string. """ def postorder(root: TreeNode) -> List[int]: return postorder(root.left) + postorder(root.right) + [root.val] if root else [] return ' '.join(map(str, postorder(root)))def deserialize(self, data: str) -> TreeNode: """Decodes your encoded data to tree. """ def helper(lower:int = float('-inf'), upper:int = float('inf')) -> TreeNode: if not data or data[-1] < lower or data[-1] > upper: return None val = data.pop() root, root.right, root.left = TreeNode(val), helper(val, upper), helper(lower, val) return root data = https://www.it610.com/article/[int(x) for x in data.split(' ') if x] return helper()# Your Codec object will be instantiated and called as such: # Your Codec object will be instantiated and called as such: # ser = Codec() # deser = Codec() # tree = ser.serialize(root) # ans = deser.deserialize(tree) # return ans