JZ37 序列化二叉树

描述

请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。

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

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

示例

输入：

{1,2,3,#,#,6,7}

返回值：

{1,2,3,#,#,6,7}

说明：输入一颗二叉树，调用序列化后生成字符串，再调用反序列化将字符串还原为树输出，输入和输出的树应相同。

解析

这题要求很明确，可以理解为要求用字符串来保存树的信息，即能根据字符串生成树。这个字符串保存的树的信息可以是先序、中序、后序和层序的，在第一眼看到这题时，我想的是用层序的方式去做。

层序方式

以层序顺序将树序列化，其实就是层序遍历树，遍历时在字符串中保存当前节点的信息，这倒是非常简单，直接就写出来了

代码清单：层序序列化

import java.util.Queue;
import java.util.LinkedList;

public class Solution {
    // 将树序列化为字符串，此处采用层序遍历的顺序
    String Serialize(TreeNode root) {
        StringBuilder treeStr = new StringBuilder("");
        if(root == null)
            return treeStr.toString();
        Queue queue = new LinkedList<>();
        queue.offer(root);
        TreeNode temp = null;
        while(!queue.isEmpty()){
            temp = queue.poll();
            if(temp == null){
                treeStr.append("#");
                treeStr.append(",");
            }else{
                treeStr.append(temp.val); // 会自动转换的吧？
                treeStr.append(",");
                queue.offer(temp.left);
                queue.offer(temp.right);
            }
        }
        treeStr.deleteCharAt(treeStr.length() - 1);
        return treeStr.toString();
    }
    
    ...
        
}

其中用到了 StringBuilder 对象以动态地修改字符串，它是线程不安全的，但执行速度快；StringBuffer 是线程安全的，但执行速度慢（现在用的很少了）。

这段代码就是在层序遍历中加上了对字符串的操作，没什么难点。不过有一个问题，即输入这样一棵树

{1,2,3,#,#,6,7}

调用这段序列化代码后，生成的字符串为（括号加上去好看）

{1,2,3,#,#,6,7,#,#,#,#}

后面的4个 # 符号表明节点 6 和 7 的孩子节点为空，看起来没问题，但当输入的树的叶子结点很多的时候，这样会不会有点浪费空间？一时半会也没想到解决的方法。

将层序序列化后得到的字符串还原为树，就需要一点想法了。我的想法是：在二叉树中，任何节点都有两个子节点，即总节点数应该是 2n+1，其中1为根节点。也就是说，先将根节点放入队列中，剩下偶数个节点，可以通过两个子节点对应一个队列中节点（不为空）的方式，将序列中的节点接到树上。

代码清单：层序反序列化

public class Solution {
    
    ...
    
    TreeNode Deserialize(String str) {
        TreeNode root = null;
        if(str.equals(""))
           return root;
        Queue queue = new LinkedList<>();
        //将序列化之后的序列用，分隔符转化为数组
        String[] s = str.split(",");
        int num = 0;
        root = new TreeNode(Integer.parseInt(s[num]));
        num++;
        queue.offer(root);
        while(num < s.length){
            TreeNode temp = queue.poll();
            if(temp == null)
                continue;
            // 策略：两个节点换一个节点
            TreeNode left, right;
            if(s[num].equals("#"))
                left = null;
            else
                left = new TreeNode(Integer.parseInt(s[num]));
            num++;
            if(s[num].equals("#"))
                right = null;
            else
                right = new TreeNode(Integer.parseInt(s[num]));
            num++;
            if(left != null)
                temp.left = left;
            if(right != null)
                temp.right = right;
            queue.offer(left);
            queue.offer(right);
        }
        return root;
    }
}

在一次循环中，会从序列中获取两个节点，将它们接到队列中出队的节点上。若当前出队的节点为空，则直接进入下一个循环，让下一个节点出队，否则在遇到只有一个孩子节点的树时会出问题（被坑了）

{5,4,#,3,#,2}

以层序的顺序序列化和反序列化就是这样，思路简单，但实际代码写起来有点复杂，在看了递归的方式后，我只能说，层序，狗都不用！

先序方式

再来看看按照先序的顺序进行序列化和反序列化。

既然是先序，就肯定涉及到递归了。递归的思路为，可以将每个节点都看成一颗子树，每颗子树都对应了一个序列，直到叶子结点，它的序列就是一个字符串（只包含自身信息，没有分割的字符串）！

代码清单：先序序列化

public class Solution {
    
    String Serialize(TreeNode root) {
        if (root == null)
            return "#";
        else
            return root.val + "," + Serialize(root.left) + "," + Serialize(root.right);
    }
    
    ...
        
}

比起层序，代码实现不要简单太多，虽然思路相比起来有点难想到，只能说，要多想！

利用先序的序列反序列化时，由于不想再写一个方法将索引以参数传递，所以需要定义一个类变量 index 充当索引，这样在递归的过程中每次调用都能访问到它。

代码清单：层序反序列化

public class Solution {
    
    int index = -1;
    
    String Serialize(TreeNode root) {
        if (root == null)
            return "#";
        else
            return root.val + "," + Serialize(root.left) + "," + Serialize(root.right);
    }
    
    TreeNode Deserialize(String str) {
        //将序列化之后的序列用，分隔符转化为数组
        String[] s = str.split(",");
        // 每进入一个节点，索引就 +1，获取数组中它的信息
        index++;
        int len = s.length;
        if (index > len) {
            return null;
        }
        TreeNode treeNode = null;
        // 当前节点不为空，则需要给它赋予对应的信息
        if (!s[index].equals("#")) {
            treeNode = new TreeNode(Integer.parseInt(s[index]));
            treeNode.left = Deserialize(str);
            treeNode.right = Deserialize(str);
        }
        // 如果节点为空直接返回的就是 null
        return treeNode;
    }
}

具体的递归过程为，获取当前节点的信息，若为空则直接返回，不为空则给该节点赋予其对应的信息，然后对其孩子节点递归调用反序列化方法。

总结

比起层序，先序的代码实现、代码思路都更清晰，但在思考的时候稍难一点；虽然层序思考简单，但那写出来的代码，第二次看都不知道能不能看懂！

这题还是比较有应用意义的，通过字符串保存一颗树的信息??！

题目笔记数据结构：树

JZ37 序列化二叉树