serialize-and-deserialize-binary-tree.go

// https://leetcode.com/problems/serialize-and-deserialize-binary-tree

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

import "strconv"

type Codec struct {
}

func Constructor() Codec {
	return Codec{}
}

// Serializes a tree to a single string.
func (c *Codec) serialize(root *TreeNode) string {
	if root == nil {
		return "[null]"
	}

	queue := []*TreeNode{root}
	serialized := ""

	for len(queue) > 0 {
		top := queue[0]
		queue = queue[1:]

		if top == nil {
			serialized = fmt.Sprintf("%s,null", serialized)
			continue
		}

		if len(serialized) > 0 {
			serialized = fmt.Sprintf("%s,%d", serialized, top.Val)
		} else {
			serialized = fmt.Sprintf("%d", top.Val)
		}

		queue = append(queue, top.Left)
		queue = append(queue, top.Right)
	}

	return "[" + serialized + "]"
}

// Deserializes your encoded data to tree.
func (c *Codec) deserialize(data string) *TreeNode {
	if len(data) == 0 || data == "[null]" {
		return nil
	}

	root := &TreeNode{}
	_, _ = fmt.Sscanf(data[1:], "%d", &root.Val)
	data = skipNumber(data[1:], root.Val)

	queue := []*TreeNode{root}

	for len(queue) > 0 {
		top := queue[0]
		queue = queue[1:]

		if len(data) <= 1 {
			continue
		}

		top.Left, data = readChild(data[1:]) // exclude comma

		if len(data) > 1 {
			top.Right, data = readChild(data[1:]) // exclude comma
		}

		if top.Left != nil {
			queue = append(queue, top.Left)
		}

		if top.Right != nil {
			queue = append(queue, top.Right)
		}
	}

	return root
}

func readChild(data string) (*TreeNode, string) {
	if data[0] != 'n' {
		child := &TreeNode{}
		_, _ = fmt.Sscanf(data, "%d", &child.Val)

		return child, skipNumber(data, child.Val)
	}

	return nil, data[4:]
}

func skipNumber(data string, number int) string {
	str := strconv.Itoa(number)

	return data[len(str):]
}

/**
 * Your Codec object will be instantiated and called as such:
 * obj := Constructor();
 * data := obj.serialize(root);
 * ans := obj.deserialize(data);
 */