Skip to content

Instantly share code, notes, and snippets.

@andreis
Last active Aug 29, 2015
Embed
What would you like to do?
A somewhat obvious solution is to emulate a heap and replace the missing nodes with "x" markers, but this performs badly on path trees (only left links). An improvement would be to replace consecutive "x"-es by "x<number>", where number==how many x-es are replaced. The solution in this gist does a depth-first traversal and prints the tree recurs…
package main
import (
"fmt"
"math/rand"
"strconv"
"strings"
"time"
)
type node struct {
l, r *node
val int
}
func Serialize(n *node) string {
if n == nil {
return ""
}
out := fmt.Sprint(n.val)
if n.l == nil && n.r == nil {
return out
}
out += "("
if n.l != nil {
out += Serialize(n.l)
} else {
out += "x"
}
out += " "
if n.r != nil {
out += Serialize(n.r)
} else {
out += "x"
}
return out + ")"
}
func Deserialize(s string) *node {
out := new(node)
helper(Tokenize(s), out, false)
return out.l
}
// adds a new node (or nil) to ((isRight) ? prev.r : prev.r)
// max stack is O(h), h ∈ [logn, n]
func helper(s []string, prev *node, isRight bool) []string {
if len(s) < 1 {
return s
}
var tmp *node = new(node)
if val, err := strconv.Atoi(s[0]); err == nil {
tmp.val = val
s = s[1:]
} else if strings.ToLower(s[0]) == "x" {
return s[1:]
} else {
panic("bad format") // expected int or "x"
}
if isRight {
prev.r = tmp
} else {
prev.l = tmp
}
if len(s) < 1 || s[0] != "(" {
return s
}
s = helper(s[1:], tmp, false)
s = helper(s, tmp, true)
if len(s) < 1 || s[0] != ")" {
panic("bad format")
}
return s[1:]
}
const WS = " \t\n"
// simply turns a string into an array of ints, parens, and "x"-es
func Tokenize(s string) []string {
out := []string{}
for len(s) > 0 {
// skipping whitespace
for len(s) > 0 && strings.ContainsRune(WS, rune(s[0])) {
s = s[1:]
}
tmp := ""
for len(s) > 0 && !strings.ContainsRune(WS, rune(s[0])) {
if strings.ContainsRune("()", rune(s[0])) {
if len(tmp) == 0 {
tmp = string(s[0])
s = s[1:]
}
break
}
tmp += string(s[0])
s = s[1:]
}
if len(tmp) > 0 {
out = append(out, tmp)
}
}
return out
}
func RandTree(n int) *node {
if n == 0 {
return nil
}
tmp := new(node)
tmp.val = rand.Intn(99) + 1
cut := rand.Intn(n)
tmp.l = RandTree(cut)
tmp.r = RandTree(n - 1 - cut)
return tmp
}
func PrintTree(n *node, indent int) {
fmt.Print(strings.Repeat("└-", indent))
if n == nil {
fmt.Println("x")
return
} else {
fmt.Println(n.val)
}
if n.l == nil && n.r == nil {
return
}
PrintTree(n.l, indent+1)
PrintTree(n.r, indent+1)
}
func init() {
rand.Seed(time.Now().UnixNano())
}
func main() {
orig := RandTree(10)
PrintTree(orig, 0)
fmt.Println(Serialize(orig))
clone := Deserialize(Serialize(orig))
PrintTree(clone, 0)
fmt.Println(Serialize(clone))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment