序列化二叉树

1. 题目描述

请实现两个函数，分别用来序列化和反序列化二叉树

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

2. 思路

• 先序遍历
• 先序遍历+中序遍历

3. 实现

3.1. 先序遍历

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

    private Integer index = -1;

    String Serialize(TreeNode root)
    {
        //把遍历的结果保存到list中
        List<String> res = new ArrayList<>();
        if (root == null)
        {
            return String.join(COMMA, res);
        }

        //采用先序遍历，如果到达空节点，那么加入#
        this.preOrder(root, res);

        //把list转成string，中间用空格分隔
        return String.join(COMMA, res);
    }

    private void preOrder(TreeNode root, List<String> res)
    {
        //如果是空的节点那么使用#表示
        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)
    {
        //检查参数
        if (str == null || str.length() == 0)
        {
            return null;
        }

        //str按照,切分成list
        String[] split = str.split(COMMA);
        //使用一个变量记录当前正在构造的节点
        return this.preOrderDeserialize(split);


    }

    private TreeNode preOrderDeserialize(String[] split)
    {
        index++;
        String val = split[index];
        if (!val.equals(SHARP))
        {
            //序列化用的先序遍历，那么反序列化也是用先序遍历
            TreeNode treeNode = new TreeNode(Integer.parseInt(val));
            treeNode.left = this.preOrderDeserialize(split);
            treeNode.right = this.preOrderDeserialize(split);
            return treeNode;
        }
        return null;
    }
}

3.2. 先序遍历+中序遍历

package main

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

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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param root TreeNode类
 * @return TreeNode类
 */
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
	}
	//从pre中找到root
	rootVal, _ := strconv.Atoi(pre[0])
	root := &TreeNode{
		Val: rootVal,
	}
	//用root把vin分成两半
	var i int
	for i = 0; i < len(vin); i++ {
		if vin[i] == pre[0] {
			break
		}
	}
	leftVin := vin[:i]
	rightVin := vin[i+1:]

	//也把pre分成两半
	leftPre := pre[1:i+1]
	rightPre := pre[i+1:]

	//左子树
	root.Left = reConstruct(leftPre, leftVin)
	//右子树
	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. 参考

• 序列化二叉树_牛客网
• 重建二叉树_牛客网