Serialize a Binary Tree

1. Problem Description

Implement two functions to serialize and deserialize a binary tree respectively.

Serialization of a binary tree means saving the result of traversing a binary tree in some format as a string, so that the binary tree constructed in memory can be persisted. Serialization can be modified based on preorder, inorder, postorder, or level-order traversal of a binary tree. The serialization result is a string. During serialization, some symbol is used to represent an empty node (#), and ! indicates the end of a node value (value!).

Deserialization of a binary tree means reconstructing the binary tree from the serialized string result str obtained according to some traversal order.

2. Approach

• Preorder traversal
• Preorder traversal + inorder traversal

3. Implementation

3.1. Preorder Traversal

public class 序列化二叉树
{
    private static final String SHARP = "#";
    private static final String COMMA = ",";

    private Integer index = -1;

    String Serialize(TreeNode root)
    {
        // Save the traversal result in a list
        List<String> res = new ArrayList<>();
        if (root == null)
        {
            return String.join(COMMA, res);
        }

        // Use preorder traversal; add # when an empty node is reached
        this.preOrder(root, res);

        // Convert the list to a string, separated by spaces
        return String.join(COMMA, res);
    }

    private void preOrder(TreeNode root, List<String> res)
    {
        // Use # to represent an empty node
        if (root == null)
        {
            res.add(SHARP);
            return;
        }

        res.add(String.valueOf(root.val));
        this.preOrder(root.left, res);
        this.preOrder(root.right, res);

    }

    TreeNode Deserialize(String str)
    {
        // Check parameters
        if (str == null || str.length() == 0)
        {
            return null;
        }

        // Split str into a list by commas
        String[] split = str.split(COMMA);
        // Use a variable to record the node currently being constructed
        return this.preOrderDeserialize(split);


    }

    private TreeNode preOrderDeserialize(String[] split)
    {
        index++;
        String val = split[index];
        if (!val.equals(SHARP))
        {
            // Serialization uses preorder traversal, so deserialization also uses preorder traversal
            TreeNode treeNode = new TreeNode(Integer.parseInt(val));
            treeNode.left = this.preOrderDeserialize(split);
            treeNode.right = this.preOrderDeserialize(split);
            return treeNode;
        }
        return null;
    }
}

3.2. Preorder Traversal + Inorder Traversal

package main

import (
	"fmt"
	"strconv"
	"strings"
)

/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * The class name, method name, and parameter names in the code have already been specified. Do not modify them; directly return the value required by the method.
 *
 * @param root TreeNode class
 * @return TreeNode class
 */
func Serialize(root *TreeNode) *TreeNode {
	str := serialize(root)

	return deserialize(str)
}

func deserialize(str string) *TreeNode {
	datas := strings.Split(str, " ")
	pre := datas[:len(datas)/2]
	mid := datas[len(datas)/2:]

	return reConstruct(pre, mid)
}

func reConstruct(pre []string, vin []string) *TreeNode {
	if len(pre) == 0 || len(vin) == 0 {
		return nil
	}
	// Find the root from pre
	rootVal, _ := strconv.Atoi(pre[0])
	root := &TreeNode{
		Val: rootVal,
	}
	// Split vin into two parts using root
	var i int
	for i = 0; i < len(vin); i++ {
		if vin[i] == pre[0] {
			break
		}
	}
	leftVin := vin[:i]
	rightVin := vin[i+1:]

	// Also split pre into two parts
	leftPre := pre[1:i+1]
	rightPre := pre[i+1:]

	// Left subtree
	root.Left = reConstruct(leftPre, leftVin)
	// Right subtree
	root.Right = reConstruct(rightPre, rightVin)
	return root
}

func serialize(root *TreeNode) string {
	if root == nil {
		return ""
	}

	preOrderData := make([]int, 0)
	preOrder(root, &preOrderData)

	midOrderData := make([]int, 0)
	midOrder(root, &midOrderData)

	str := ""
	for _, data := range preOrderData {
		str += fmt.Sprintf("%v ", data)
	}

	for _, data := range midOrderData {
		str += fmt.Sprintf("%v ", data)
	}

	str = strings.TrimRight(str, " ")
	return str
}

func midOrder(root *TreeNode, midOrderData *[]int) {
	if root == nil {
		return
	}

	midOrder(root.Left, midOrderData)
	*midOrderData = append(*midOrderData, root.Val)
	midOrder(root.Right, midOrderData)
}

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

	*preOrderData = append(*preOrderData, root.Val)
	preOrder(root.Left, preOrderData)
	preOrder(root.Right, preOrderData)
}

4. References

• Serialize Binary Tree - NowCoder
• Reconstruct Binary Tree - NowCoder