推荐

完整《剑指Offer》算法题解析系列请点击 👉 《剑指Offer》全解析 Java 版

题目描述

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

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

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

例如，我们可以把一个只有根节点为1的二叉树序列化为"1,"，然后通过自己的函数来解析回这个二叉树

/* 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) {
   
       
  }
}

思路： 递归

实现：

/* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
public class Solution {
   
    
    private String deserializeStr;
    
    //前序遍历（中左右），序列化二叉树
    String Serialize(TreeNode root) {
   
        //如果是空结点，则返回 #
        if (root == null) {
   
            return "#";
        }
        //如果不是空结点，则返回该结点的值和该结点的左右子结点
        return root.val + "!" + Serialize(root.left) + "!" + Serialize(root.right);
  }
    //反序列化二叉树
    TreeNode Deserialize(String str) {
   
        deserializeStr = str;
        return Deserialize();
  }
    
    private TreeNode Deserialize() {
   
        //如果字符串长度为0，直接返回null
        if (deserializeStr.length() == 0) {
   
            return null;
        }
        
        //找到字符串中第一个 ! 的位置，也就是字符串中树的第一个结点后面的位置。
        int  index = deserializeStr.indexOf("!");
        
        //创建一个 node 字符串准备来存储结点
        String node = "";
        
        //如果字符串中没有 ! ,那说明已经没有字符串中已经没有树的结点了，直接将字符串整个存入node
        if (index == -1) {
   
             node = deserializeStr;
        } else {
    //如果字符串中有 ! ,那么说明还有结点，将 ! 前的那个结点存入node。
             node = deserializeStr.substring(0, index);
        }
        
        //判断字符串中是否有结点，有的话，从该结点后面的 ! 开始截取剩下的字符串。
        if (index == -1) {
   
            deserializeStr="";
        } else {
   
            deserializeStr = deserializeStr.substring(index + 1);
        }
        
        //如果这个node结点是 # ，说明是空结点，返回 null
        if (node.equals("#")) {
   
            return null;
        }
        
        //如果不是空结点
        //先将 node 字符串中的数字转换成 int 型的结点值。
        int val = Integer.valueOf(node);
        //用该结点值构建一个二叉树的结点
        TreeNode t = new TreeNode(val);
        //递归构造左子树
        t.left = Deserialize();
        //递归构造右子树
        t.right = Deserialize();
        //返回树的的结点
        return t;
        
    }    
    
}

附录：

int indexOf(String str) : 返回指定字符在字符串中第一次出现处的索引，如果此字符串中没有这样的字符，则返回 -1。

substring(int beginIndex) : 返回字符串的子字符串，字符串的从下标 beginIndex 到结尾的子字符串（包括 beginIndex 下标的字符）。
    
substring(int beginIndex, int endIndex) : 返回字符串的子字符串，字符串的从下标 beginIndex 到下标 endIndex 的子字符串（包括 beginIndex 下标的字符,不包括 endIndex 下标的字符串）。

看完之后，如果还有什么不懂的，可以在评论区留言，会及时回答更新。

这里是猿兄，为你分享程序员的世界。

非常感谢各位大佬们能看到这里，如果觉得文章还不错的话， 求点赞👍 求关注💗 求分享👬求评论📝 这些对猿兄来说真的 非常有用！！！

注： 如果猿兄这篇博客有任何错误和建议，欢迎大家留言，不胜感激！