序列化和反序列化二叉树

题目描述

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

/*
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….