《剑指offer》 第37题 序列化二叉树

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

  二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过某种符号表示空节点（#），以 ！表示一个结点值的结束（value!）。
  二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
  小白看这两段解释肯定看不明白，别问我怎么知道的。看图，下图是一个前序遍历的序列化示例。来自于剑指offer书上。只不过#换成了$。

通过序列化的这个串，很容易反序列化重建成二叉树，因为空节点都标记了出来，之前做过二叉树的重建就能知道，根据前序和中序遍历的结果重建二叉树时，使用到了两个序列，因为你需要判断节点位置，而当空节点被标记时，就能很清楚节点的位置，因此反序列化时一个序列就能重建二叉树了。

  在频繁操作字符串时，最好使用StringBuffer或者StringBuilder。由于序列号的前中后序以及层次都可以修改，所以递归，栈，队列都可以使用。
1.递归写法
不仅使用了StringBuilder代替了String，并且还在反序列化时，没有进行切割动作，而是选取一个数组范围进行比较，看是否有包含#，这就导致一个角标变量应该设置为全局变量。

public class Solution {
    String Serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if (root == null) {
            sb.append("#!");//当今节点为空，就添加一个#做标记
        } else {
            sb.append(root.val + "!");//前序遍历根节点
            sb.append(Serialize(root.left));//然后调用左子树递归
            sb.append(Serialize(root.right));//最后调用右子树递归
        }
        return sb.toString();
  }
    int index = 0;//字符串数组的角标
    TreeNode Deserialize(String str) {
       TreeNode node = null;
        if (str == null || str.length() == 0)
            return node;
        int start = index;
        while (str.charAt(index) != '!')
            index++;//这index++是为了跳过当前字符，此时指向每个字符后面的！
            if (!str.substring(start, index).equals("#")) {
                node = new TreeNode(Integer.parseInt(str.substring(start, index)));
                index++; // 这条语句位置别放错了，插入一个节点后，index++，然后再递归
                node.left = Deserialize(str);
                node.right = Deserialize(str);
            } else {
                index++;//否则当前字符串为#，就是空的，直接index++，不操作。
        }
        return node;
  }
}

2.非递归写法，我自己是没写出来。摘的另一篇题解，一叶浮尘大佬的回答，供自己学习。

链接：https://www.nowcoder.com/questionTerminal/cf7e25aa97c04cc1a68c8f040e71fb84?answerType=1&f=discussion
来源：牛客网
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    String Serialize(TreeNode root) {
        StringBuilder result = new StringBuilder("");
        if(root != null){
            //先访问根节点
            result.append(String.valueOf(root.val));
            //offer poll peek
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.offer(root);//需要根据队列中存储的元素来作为访问下一个节点的依据。
            while(!queue.isEmpty()){
                //把队列元素的左右子树进行访问，然后加入到队列中。
                TreeNode head = queue.poll();
                if(head.left!= null || head.right!= null){
                    if(head.left == null)
                        result.append(",#");
                    else{
                        result.append("," + String.valueOf(head.left.val));
                        queue.offer(head.left);
                    }

                    if(head.right == null)
                        result.append(",#");
                    else{
                        result.append("," + String.valueOf(head.right.val));
                        queue.offer(head.right);
                    }
                }else{
                    //该节点为叶子节点，不需要进行任何处理。
                }
            }
        }
        return result.toString();

  }
    TreeNode Deserialize(String str) {
        TreeNode root = null;
        if(!str.equals("")){
            String[] list = str.split(",");
               //先建立根节点
            root = new TreeNode(Integer.parseInt(list[0]));
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.offer(root);
//把需要插入左右节点的元素放在队列中管理，一旦左右子树建立之后就从队列中移除
            int index = 1;
            while(!queue.isEmpty() && index < list.length){
               TreeNode temp = queue.poll();
               if(!list[index].equals("#")){
                    TreeNode newLeft = new TreeNode(Integer.parseInt(list[index]));
                    temp.left = newLeft;
                    index ++;
                    queue.offer(newLeft);
                 }else
                     index ++;//所有的if都应该配备else，不然真的很容易出错误

                if(index < list.length && !list[index].equals("#")){
                    TreeNode newRight = new TreeNode(Integer.parseInt(list[index]));
                    temp.right = newRight;
                    index ++;
                    queue.offer(newRight);
                  }else
                     index++;//所有的if都应该配备else，不然真的很容易出错误
                }
            }
        return root;
    }
}