Serialize and Deserialize Binary Tree

1. Problem Description

Serialization converts a data structure or object into a continuous representation so the result can be stored in a file or memory, transmitted over a network, and later reconstructed by the reverse operation.

Design an algorithm to serialize and deserialize a binary tree. The serialization/deserialization logic is not constrained; you only need to ensure that a binary tree can be serialized to a string and deserialized back into the original tree structure.

2. Approach

1. Approach 1
   • Level-order traversal
   • Serialization: if a node is null, append the symbol 'X' to the res array; otherwise append the node value to res and enqueue its left and right children
   • Deserialization: take parent nodes from the level-order queue in sequence and use index to read their left and right children in order; i, i+1, and i+2 cannot be used as a fixed positional relationship
2. Approach 2: Similar to Construct Binary Tree from Preorder and Inorder Traversal, but this approach is incorrect

3. Implementation

3.1. Level-Order Traversal

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

type Codec struct {
}

func Constructor() Codec {
	return Codec{
	}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	res := make([]string, 0)
	for len(queue) > 0 {
		n := queue[0]
		queue = queue[1:]

		if n != nil {
			res = append(res, strconv.Itoa(n.Val))
			queue = append(queue, n.Left)
			queue = append(queue, n.Right)
		} else {
			res = append(res, "X")
		}
	}

	return strings.Join(res, ",")
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
	if data == "X" {
		return nil
	}
	list := strings.Split(data, ",")
	rootVal, _ := strconv.Atoi(list[0])
	root := &TreeNode{Val: rootVal}
	queue := []*TreeNode{root}
	index := 1

	for index < len(list) {
		node := queue[0]
		queue = queue[1:]
		leftVal := list[index]
		rightVal := list[index+1]
		if leftVal != "X" {
			v, _ := strconv.Atoi(leftVal)
			leftNode := &TreeNode{Val: v}
			node.Left = leftNode
			queue = append(queue, leftNode)
		}
		if rightVal != "X" {
			v, _ := strconv.Atoi(rightVal)
			rightNode := &TreeNode{Val: v}
			node.Right = rightNode
			queue = append(queue, rightNode)
		}
		index += 2
	}
	return root

}

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

3.2. Preorder + Inorder (Incorrect)

type Codec struct {
}

func Constructor() Codec {
	return Codec{
	}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
	preorder := make([]string, 0)
	preOrder(root, &preorder)

	inorder := make([]string, 0, len(preorder))
	inOrder(root, &inorder)

	if len(preorder) == 0 {
		return ""
	}

	pre := strings.Join(preorder, ":")
	mid := strings.Join(inorder, ":")
	return pre + "_" + mid
}

func inOrder(root *TreeNode, vals *[]string) {
	if root == nil {
		return
	}

	inOrder(root.Left, vals)
	*vals = append(*vals, strconv.Itoa(root.Val))
	inOrder(root.Right, vals)
}

func preOrder(root *TreeNode, vals *[]string) {
	if root == nil {
		return
	}

	*vals = append(*vals, strconv.Itoa(root.Val))
	preOrder(root.Left, vals)
	preOrder(root.Right, vals)
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
	if data == "" {
		return nil
	}

	split := strings.Split(data, "_")
	preorder := make([]int, 0)
	pre := strings.Split(split[0], ":")
	for _, v := range pre {
		num, _ := strconv.Atoi(v)
		preorder = append(preorder, num)
	}
	inorder := make([]int, 0)
	mid := strings.Split(split[1], ":")
	for _, v := range mid {
		num, _ := strconv.Atoi(v)
		inorder = append(inorder, num)
	}

	return buildTree(preorder, inorder)
}

func buildTree(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 || len(inorder) == 0 { return nil }
	rootVal := preorder[0]
	idx := find(inorder, rootVal)
	root := &TreeNode{Val: rootVal}
	root.Left = buildTree(preorder[1:idx+1], inorder[:idx])
	root.Right = buildTree(preorder[idx+1:], inorder[idx+1:])
	return root
}

func find(nums []int, target int) int {
	for i, num := range nums {
		if num == target { return i }
	}
	return -1
}

4. References

• Hand-Drawn Explanation of DFS and BFS Solutions | Serialize and Deserialize Binary Tree - LeetCode