- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
关键词:力扣,LeetCode,算法,题解,解析,449,Python, C++, 二叉搜索树,序列化,反序列化
题目地址:https://leetcode.cn/problems/serialize-and-deserialize-bst/open in new window
序列化是将数据结构或对象转换为一系列位的过程,以便它可以存储在文件或内存缓冲区中,或通过网络连接链路传输,以便稍后在同一个或另一个计算机环境中重建。
设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串,并且可以将该字符串反序列化为最初的二叉搜索树。
编码的字符串应尽可能紧凑。
示例1:
输入:root = [2,1,3]
输出:[2,1,3]
示例2:
输入:root = []
输出:[]
提示:
<= Node.val
<= 10^4来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/serialize-and-deserialize-bst 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
首先要明白题意:
题目没有限定我们用什么方法,只要求我们序列化后的字符串尽可能紧凑。
解法不固定,只要序列化后的结果,能被反序列化函数还原成一模一样的二叉搜索树(BST),都认为是正确答案。
评测的过程是下面这样:
Codec ser = new Codec();
Codec deser = new Codec();
String tree = ser.serialize(root);
TreeNode ans = deser.deserialize(tree);
return ans;
1 2 3 4 5
BST的基本定义:
只知道树的一种遍历方式,是没法确定这个树的,BST 也不例外。
因此,我的主要思路就是:采用前序遍历的序列化 BST,再根据 BST 的性质进行反序列化。
1、 序列化的过程:
采用前序遍历,转化成字符串。
1、 反序列化的过程:
Python语言代码如下:
# 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):
vals = []
def preOrder(root):
if root:
vals.append(root.val)
preOrder(root.left)
preOrder(root.right)
preOrder(root)
return ','.join(map(str, vals))
def deserialize(self, data):
if not data or data == '':
return None
vals = map(int, data.split(","))
root = TreeNode(vals[0])
leftVals = [x for x in vals if x < vals[0]]
rightVals = [x for x in vals if x > vals[0]]
root.left = self.deserialize(",".join(map(str, leftVals)))
root.right = self.deserialize(",".join(map(str, rightVals)))
return root
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# tree = ser.serialize(root)
# ans = deser.deserialize(tree)
# return ans
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
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 {
public:
void preOrder(TreeNode* root, vector<int>& res) {
if (!root) return;
res.push_back(root->val);
preOrder(root->left, res);
preOrder(root->right, res);
}
string vector2string(vector<int>& vals) {
string res;
if (vals.empty()) return res;
for (int i = 0; i < vals.size() - 1; ++i) {
res += to_string(vals[i]) + ",";
}
res += to_string(vals[vals.size() - 1]);
return res;
}
vector<int> split(string& s) {
vector<int> res;
size_t pos = 0;
std::string token;
while ((pos = s.find(",")) != std::string::npos) {
token = s.substr(0, pos);
res.push_back(stoi(token));
s.erase(0, pos + 1);
}
res.push_back(stoi(s));
return res;
}
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
vector<int> vals;
preOrder(root, vals);
return vector2string(vals);
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if (data.empty()) return nullptr;
vector<int> vals = split(data);
TreeNode* root = new TreeNode(vals[0]);
vector<int> leftVals;
vector<int> rightVals;
for (int val : vals) {
if (val < vals[0]) {
leftVals.push_back(val);
} else if (val > vals[0]) {
rightVals.push_back(val);
}
}
root->left = deserialize(vector2string(leftVals));
root->right = deserialize(vector2string(rightVals));
return root;
}
};
// 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;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
复杂度:
在反序列化的过程中,也可以通过一个队列进行操作。
python 代码如下:
# 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
"""
vals = []
def preOrder(root):
if root:
vals.append(root.val)
preOrder(root.left)
preOrder(root.right)
preOrder(root)
return ' '.join(map(str, vals))
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
vals = collections.deque(int(val) for val in data.split())
def build(minVal, maxVal):
if vals and minVal < vals[0] < maxVal:
val = vals.popleft()
root = TreeNode(val)
root.left = build(minVal, val)
root.right = build(val, maxVal)
return root
return build(float('-inf'), float('inf'))
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
1、 没有固定套路的题目,需要自己发掘数据结构的性质,找到合适的解法;
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
我已经编写了一个 BSTLink 类来将 BST 转换为双向链表,但是在我尝试通过引用传递 BST 的节点指针的类中的构造调用抛出一个错误“没有匹配的函数来调用 BSTLink::construct(
当我使用 xgboost 为 2-cates classification problem 训练我的数据时,我想使用提前停止来获得最佳模型,但我对在我的预测中使用哪一个感到困惑,因为提前停止将返回 3
因为我找不到有用的东西所以我在这里问我的问题: 我们如何在不使用任何额外空间的情况下将 BST 转换为中序链接列表,然后再转换回“相同”的 BST。 到目前为止我已经尝试过的(虽然仍在做):我尝试了
我从我们的教授讲座幻灯片中获得了 BST(二叉搜索树)和随机 BST 的源代码,现在我想通过插入新元素来测试它们是否正常工作,然后我如何才能看到我的结果,如 http://cs.lmu.edu/~ra
给定两棵二叉树 T1 和 T2,您必须找到要在 T1 中完成的最少插入次数,以使其在结构上与 T2 相同。如果不可能则返回 -1。 注意事项 假设插入在 BST 中以正常方式完成。 假设在插入时,如果
我有一个始终将日期存储为 UTC 的网络应用程序,但它们需要分别以 GMT/BST 的形式显示给用户。 我有一个 UTC/GMT 日期(2013 年 3 月 30 日 22:00),我每小时移动一次以
题目地址:https://leetcode-cn.com/problems/largest-bst-subtree/ 题目描述 Given a binary tree, find the larg
注意:BST - 二叉搜索树(缩写) 正如标题所说,这是一项家庭作业,所以我不是在寻找答案。相反,我只需要一个正确方向的点。 对于作业,我应该创建一个 BST 类,它直接定义为最多包含 2 个 BST
我有一个插入方法和一个搜索方法,我正在考虑一种方法来循环二叉搜索树并使用像获取节点这样的方法,然后在另一个二叉搜索树上搜索它,如果它成立,那么我将其插入该元素,但问题是我无法想出一种基于索引获取节点的
function validateBst(root, min=-Infinity, max=Infinity) { if (!root) return true; if (root.value
我有一个问题,我知道如何像这样计算树中的所有节点 return 1 + rightchild(tree->right) + rightchild(tree->left); 现在我的问题是如果一个节点在
给定一个二叉树根,任务是返回 任何子树的所有键的最大总和 这也是 二叉搜索树 (BST) . 假设 BST 定义如下: - 节点的左子树仅包含键小于节点键的节点。 - 节点的右子树仅包含键大于节点键的
我正在尝试使用 ScalaCheck 为 BST 创建一个 Gen,但是当我调用 .sample 方法时,它给了我 java.lang.NullPointerException。我哪里错了? seal
这些是我的领域: public class BSTSet extends AbstractSet { // Data fields private BSTNode root;
我需要在二叉搜索树中执行范围搜索功能,这将给出给定范围内的项目数量。我不明白如何在找到项目时增加计数值。因为,我必须使用递归函数&如果我在递归过程中将计数变量初始化为0,它将始终从0开始计数值,而不是
所以我正在尝试编写一个代码来返回二叉搜索树中的最小值。我知道这是树的最左边的值,并且我知道我需要它递归地向左运行,直到什么都没有为止。但是我的代码不起作用,我不知道为什么。任何帮助将不胜感激。 (de
我想返回一个包含树中所有键的字符串,按照它们的存储顺序。每个子树中的键应包含在括号中。 _7_ / \ _3_ 8 / \ 1
尝试运行递归算法来找出某棵树是否是 BST(二叉搜索树)。 boolean checkBST(Node root) { boolean isBST = true; if(root ==
使用下面的代码,每个时区都正确打印值,除了 BST import java.text.*; def format = "yyyy-MM-dd HH:mm:ssXXX" def dt = new Da
您能帮忙搜索功能吗,它总是返回nil,我不明白为什么 func BTreeSearchItem(root *TreeNode, elem string) *TreeNode { if root
我是一名优秀的程序员,十分优秀!