-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path1028.go
44 lines (41 loc) · 881 Bytes
/
1028.go
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
package main
import (
"strconv"
"strings"
)
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func recoverFromPreorder(S string) *TreeNode {
return inner(S, "-")
}
func inner(S string, prefix string) *TreeNode {
// 找到根节点
var cur string
for i := 0; i < len(S); i++ {
if S[i] == '-' {
break
} else {
cur += string(S[i])
}
}
num, _ := strconv.Atoi(cur)
root := &TreeNode{Val: num}
left := len(cur) + len(prefix)
for i := left; i < len(S); i++ {
if strings.HasPrefix(S[i:], prefix) && !strings.HasPrefix(S[i:], prefix+"-") && S[i-1] != '-' {
// 到右节点
root.Left = inner(S[left:i], prefix+"-")
root.Right = inner(S[i+len(prefix):], prefix+"-")
break
} else if i == len(S)-1 {
root.Left = inner(S[left:], prefix+"-")
}
}
return root
}