Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commita1d39b8

Browse files
authored
Merge pull request6boris#462 from 0xff-dev/449
Add solution and test-cases for problem 449
2 parents4344bcd +fead008 commita1d39b8

File tree

3 files changed

+125
-26
lines changed

3 files changed

+125
-26
lines changed

‎leetcode/401-500/0449.Serialize-and-Deserialize-BST/README.md

Lines changed: 11 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1,28 +1,25 @@
11
#[449.Serialize and Deserialize BST][title]
22

3-
>[!WARNING|style:flat]
4-
>This question is temporarily unanswered if you have good ideas. Welcome to[Create Pull Request PR](https://github.com/kylesliu/awesome-golang-algorithm)
5-
63
##Description
4+
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.
5+
6+
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.
7+
8+
**The encoded string should be as compact as possible**.
79

810
**Example 1:**
911

1012
```
11-
Input:a ="11", b = "1"
12-
Output:"100"
13+
Input:root =[2,1,3]
14+
Output:[2,1,3]
1315
```
1416

15-
##题意
16-
>...
17+
**Example 2:**
1718

18-
##题解
19-
20-
###思路1
21-
>...
22-
Serialize and Deserialize BST
23-
```go
2419
```
25-
20+
Input: root = []
21+
Output: []
22+
```
2623

2724
##结语
2825

Lines changed: 97 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,100 @@
11
package Solution
22

3-
funcSolution(xbool)bool {
4-
returnx
3+
import (
4+
"fmt"
5+
"sort"
6+
"strconv"
7+
"strings"
8+
)
9+
10+
typeTreeNodestruct {
11+
Valint
12+
Left,Right*TreeNode
13+
}
14+
typeCodecstruct {
15+
}
16+
17+
funcConstructor()Codec {
18+
returnCodec{}
19+
}
20+
func (this*Codec)preOrder(root*TreeNode) []int {
21+
ifroot==nil {
22+
returnnil
23+
}
24+
ans:=make([]int,0)
25+
l:=this.preOrder(root.Left)
26+
r:=this.preOrder(root.Right)
27+
ans=append(ans,root.Val)
28+
ans=append(ans,l...)
29+
ans=append(ans,r...)
30+
returnans
31+
}
32+
33+
// Serializes a tree to a single string.
34+
func (this*Codec)serialize(root*TreeNode)string {
35+
ifroot==nil {
36+
return""
37+
}
38+
pre:=this.preOrder(root)
39+
dst:=make([]int,len(pre))
40+
copy(dst,pre)
41+
sort.Ints(dst)
42+
buf:= strings.Builder{}
43+
fori:=0;i<len(pre);i++ {
44+
ifi!=0 {
45+
buf.WriteByte(',')
46+
}
47+
buf.WriteString(fmt.Sprintf("%d",pre[i]))
48+
}
49+
buf.WriteByte('#')
50+
fori:=0;i<len(dst);i++ {
51+
ifi!=0 {
52+
buf.WriteByte(',')
53+
}
54+
buf.WriteString(fmt.Sprintf("%d",dst[i]))
55+
}
56+
returnbuf.String()
57+
}
58+
59+
// Deserializes your encoded data to tree.
60+
func (this*Codec)deserialize(datastring)*TreeNode {
61+
ifdata=="" {
62+
returnnil
63+
}
64+
builder:=strings.Split(data,"#")
65+
iflen(builder)!=2 {
66+
returnnil
67+
}
68+
pre:=strings.Split(builder[0],",")
69+
in:=strings.Split(builder[1],",")
70+
returnthis.buildTree(pre,in)
71+
}
72+
73+
func (this*Codec)buildTree(pre,in []string)*TreeNode {
74+
iflen(pre)==1 {
75+
v,_:=strconv.Atoi(pre[0])
76+
return&TreeNode{Val:v}
77+
}
78+
79+
v:=pre[0]
80+
index:=0
81+
for ;index<len(pre)&&in[index]!=v;index++ {
82+
}
83+
84+
vv,_:=strconv.Atoi(v)
85+
node:=&TreeNode{Val:vv}
86+
ifindex>0 {
87+
node.Left=this.buildTree(pre[1:index+1],in[:index])
88+
}
89+
ifindex<len(pre)-1 {
90+
node.Right=this.buildTree(pre[index+1:],in[index+1:])
91+
}
92+
returnnode
93+
}
94+
95+
funcSolution(tree*TreeNode) (*TreeNode,string) {
96+
c:=Constructor()
97+
s:=c.serialize(tree)
98+
t:=c.deserialize(s)
99+
returnt,s
5100
}

‎leetcode/401-500/0449.Serialize-and-Deserialize-BST/Solution_test.go

Lines changed: 17 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -10,30 +10,37 @@ func TestSolution(t *testing.T) {
1010
//测试用例
1111
cases:= []struct {
1212
namestring
13-
inputsbool
14-
expectbool
13+
inputs*TreeNode
14+
expectstring
1515
}{
16-
{"TestCase",true,true},
17-
{"TestCase",true,true},
18-
{"TestCase",false,false},
16+
{"TestCase1",&TreeNode{
17+
Val:2,
18+
Left:&TreeNode{Val:1},
19+
Right:&TreeNode{Val:3},
20+
},"2,1,3#1,2,3"},
21+
{"TestCase2",nil,""},
1922
}
2023

2124
//开始测试
2225
fori,c:=rangecases {
2326
t.Run(c.name+" "+strconv.Itoa(i),func(t*testing.T) {
24-
got:=Solution(c.inputs)
25-
if!reflect.DeepEqual(got,c.expect) {
27+
tree,str:=Solution(c.inputs)
28+
if!reflect.DeepEqual(tree,c.inputs) {
2629
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
27-
c.expect,got,c.inputs)
30+
c.inputs,tree,c.inputs)
31+
}
32+
if!reflect.DeepEqual(str,c.expect) {
33+
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
34+
c.expect,str,c.inputs)
2835
}
2936
})
3037
}
3138
}
3239

33-
//压力测试
40+
//压力测试
3441
funcBenchmarkSolution(b*testing.B) {
3542
}
3643

37-
//使用案列
44+
//使用案列
3845
funcExampleSolution() {
3946
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp