序列化和反序列化二叉树

题目描述

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

/*public class TreeNode {    int val = 0;    TreeNode left = null;    TreeNode right = null;    public TreeNode(int val) {        this.val = val;    }}*/public class Solution {    String Serialize(TreeNode root) {          }    TreeNode Deserialize(String str) {         }}

分析

什么是二叉树的序列化和反序列化

首先我们先来了解一下什么是二叉树的序列化和反序列化

二叉树的序列化：将二叉树保存在一个文件或者数组中，能够持久化的存储

二叉树的反序列化：从文件或者数组中取出数据，重构一颗二叉树

如何实现二叉树的序列化

那么如何实现二叉树的序列化呢？我们知道二叉树有三种深度优先遍历方式：前序遍历、中序遍历、后序遍历

那么这三种遍历方式都可以实现将二叉树的序列化

基于前序遍历实现二叉树的序列化

那么接下来我们选择基于前序遍历来实现二叉树的序列化

我们用‘$’表示空节点

String Serialize(TreeNode root) {        StringBuffer stringBuffer = new StringBuffer();        SerializeSub(root, stringBuffer);        return stringBuffer.toString();    }    public void SerializeSub(TreeNode root, StringBuffer stringBuffer) {        //当遇到空节点的时候，标记为$,不再继续递归遍历        if(root == null) {            stringBuffer.append("$,");        }else {            //按照前序遍历的顺序，依次添加节点的val到stringbuffer（root->left->right）            stringBuffer.append(root.val + ",");            SerializeSub(root.left, stringBuffer);            SerializeSub(root.right, stringBuffer);        }    }

实现二叉树的反序列化

由于我们采用的是前序遍历序列化，那么同样反序列化也采用前序遍历反序列化

• 先将string按照“，”分隔符进行切割成为数组
• 从数组中读取一个字符，将之转化为root treeNode,
• 下一个字符递归转为left Node
• 再下一个节点递归转为right Node
• 如果遇到了空节点，就停下来，不再递归创建节点

前序遍历反序列化递归重建过程如下

int index = -1;    TreeNode Deserialize(String str) {        String[] arr = str.split(",");        TreeNode node = null;        index++;        if(!arr[index].equals("$")) {            node = new TreeNode(Integer.valueOf(arr[index]));            node.left = Deserialize(str);            node.right = Deserialize(str);        }        return node;    }

参考

https://javabypatel.blogspot....