資訊專欄INFORMATION COLUMN
摘要：題目要求將二叉搜索樹(shù)序列化和反序列化，序列化是指將樹(shù)用字符串的形式表示，反序列化是指將字符串形式的樹(shù)還原成原來(lái)的樣子。假如二叉搜索樹(shù)的節(jié)點(diǎn)較多，該算法將會(huì)占用大量的額外空間。
題目要求
Serialization is the process of 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 just 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. Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
將二叉搜索樹(shù)序列化和反序列化，序列化是指將樹(shù)用字符串的形式表示，反序列化是指將字符串形式的樹(shù)還原成原來(lái)的樣子。
思路和代碼對(duì)于樹(shù)的序列化，可以直接聯(lián)想到對(duì)樹(shù)的遍歷。樹(shù)的遍歷包括前序遍歷，中序遍歷，后序遍歷和水平遍歷，并且可知前序遍歷和中序遍歷，或中序遍歷和后序遍歷可以構(gòu)成一棵唯一的樹(shù)。除此以外，因?yàn)檫@是一棵二叉搜索樹(shù)，可知該樹(shù)的中序遍歷就是所有元素的從小到大的排列。
舉個(gè)例子，假如一棵樹(shù)的結(jié)構(gòu)如下：
3 / 2 4 1
該樹(shù)的前序遍歷結(jié)果為3,2,1,4，中序遍歷為1,2,3,4。再仔細(xì)分析前序遍歷的結(jié)果，結(jié)合二叉搜索樹(shù)可知，比中間節(jié)點(diǎn)小的值一定位于左子樹(shù)，反之一定位于右子樹(shù)，即可以對(duì)前序遍歷進(jìn)行分割3,|2,1,|4。也就是說(shuō)，我們可以只利用前序遍歷，就可以區(qū)分出二叉搜索樹(shù)的左子樹(shù)和右子樹(shù)。
代碼如下：
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
preorder(root, sb);
return sb.toString();
}
public void preorder(TreeNode root, StringBuilder result) {
if(root != null) {
result.append(root.val);
result.append(":");
preorder(root.left, result);
preorder(root.right, result);
}
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data==null || data.isEmpty()) return null;
String[] preorder = data.split(":");
String[] inorder = Arrays.copyOf(preorder, preorder.length);
Arrays.sort(inorder, new Comparator(){
@Override
public int compare(String o1, String o2) {
Integer i1 = Integer.valueOf(o1);
Integer i2 = Integer.valueOf(o2);
return i1.compareTo(i2);
}
});
return build(inorder, preorder, 0, 0, inorder.length);
}
public TreeNode build(String[] inorder, String[] preorder, int inorderStart, int preorderStart, int length) {
if(length <= 0) return null;
TreeNode root = new TreeNode(Integer.valueOf(preorder[preorderStart]));
for(int i = inorderStart ; i < inorderStart+length ; i++) {
if(inorder[i].equals(preorder[preorderStart])) {
root.left = build(inorder, preorder, inorderStart, preorderStart+1, i-inorderStart);
root.right = build(inorder, preorder, i+1, preorderStart+i-inorderStart+1, inorderStart+length-i-1);
break;
}
}
return root;
}
這里的代碼是直接使用排序生成了二叉搜索樹(shù)的中序遍歷的結(jié)果，并利用先序遍歷和中序遍歷構(gòu)造了一棵二叉搜索樹(shù)。假如二叉搜索樹(shù)的節(jié)點(diǎn)較多，該算法將會(huì)占用大量的額外空間?？梢灾挥孟刃虮闅v作為構(gòu)造樹(shù)的輸入，代碼如下：
public TreeNode deserialize(String data) {
if (data==null) return null;
String[] strs = data.split(":");
Queue q = new LinkedList<>();
for (String e : strs) {
q.offer(Integer.parseInt(e));
}
return getNode(q);
}
private TreeNode getNode(Queue q) {
if (q.isEmpty()) return null;
TreeNode root = new TreeNode(q.poll());//root (5)
Queue samllerQueue = new LinkedList<>();
while (!q.isEmpty() && q.peek() < root.val) {
samllerQueue.offer(q.poll());
}
root.left = getNode(samllerQueue);
root.right = getNode(q);
return root;
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/74300.html
摘要：思路理論上說(shuō)所有遍歷的方法都可以。但是為了使和的過(guò)程都盡量最簡(jiǎn)單，是不錯(cuò)的選擇。用作為分隔符，來(lái)表示。復(fù)雜度代碼思路這道題和之前不同，一般的樹(shù)變成了，而且要求是。還是可以用，還是需要分隔符，但是就不需要保存了。 297. Serialize and Deserialize Binary Tree Serialization is the process of converting a...
Problem Serialization is the process of 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 li...
摘要：題目大意將二叉樹(shù)序列化，返回序列化的，和反序列化還原。解題思路技巧在于將記錄為便于將來(lái)判斷。的思想將每一層記錄下來(lái)，反序列化時(shí)也按照層級(jí)遍歷的方法依次設(shè)置為上一個(gè)里面的元素的左孩子和右孩子。變種，可以要求輸出一個(gè)，而不是 LeetCode 297. Serialize and Deserialize Binary Tree 題目大意: 將二叉樹(shù)序列化，返回序列化的String，和反序列...
Problem Serialization is the process of 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 li...
摘要：因此題目中的例子的中序遍歷結(jié)果為。但是，標(biāo)準(zhǔn)的中序遍歷并不能使我們將該結(jié)果反構(gòu)造成一棵樹(shù)，我們丟失了父節(jié)點(diǎn)和子節(jié)點(diǎn)之間的關(guān)系。這里我們也可以明顯的看出來(lái)，中序遍歷需要保存的空值遠(yuǎn)遠(yuǎn)多于廣度優(yōu)先遍歷。 題目要求 Serialization is the process of converting a data structure or object into a sequence of ...
閱讀 3608·2023-04-26 02:24
閱讀 942·2023-04-25 14:47
閱讀 2514·2021-11-24 11:16
閱讀 1731·2021-11-24 09:38
閱讀 1583·2021-11-18 10:07
閱讀 2072·2021-09-22 15:49
閱讀 1600·2019-08-30 15:55
閱讀 890·2019-08-26 13:38
