60 序列化二叉树

题目描述

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

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

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

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

代码一

思想

1.采用层次遍历虽然易于人观察，但代码实现起来麻烦，本次借鉴leetcode官方题解，采用先序遍历实现序列化与反序列化。
2.先序遍历的按 root -> left subtree -> right subtree（根左右）的顺序递归进行，例如下面这幅图

注意：按牛客网的格式，结果应为 "1!2!3!#!#!4!#!#!5!#!#!" 即用#表示空节点，且每个节点后跟!表示结束。

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

3.现在让我们反序列化"1!2!3!#!#!4!#!#!5!#!#!" ，同样采用先序遍历的思想，为了方便观察和后续操作，我们先将其分割成数组并存入链表。[1 , 2, 3, #, #, 4, #, #, 5, #, #]
先序遍历**的数组总是可以分为三部分[ [根] , [左子树的先序序列] , [右子树的先序序列] ]，且每部分的首位元素为该部分子树的根节点。**
如 [ 1 ] 是 [2, 3, #, #, 4, #, #] [5, #, #] 的父节点。
而[ 2 ]又是[ 3, #, #] [4, #, #]的父节点
以此类推…
按照这种思想，我们写出反序列化的代码：

TreeNode Deserialize(String str) {
        String[] nodes = str.split("!");
        List<String> node_list = new LinkedList<String>(Arrays.asList(nodes));
        return rDeserialize(node_list);
    }
    TreeNode rDeserialize(List<String> node_list) {
        if(node_list.get(0).equals("#")) {
            node_list.remove(0);
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(node_list.get(0)));
        node_list.remove(0);
        root.left = rDeserialize(node_list);
        root.right = rDeserialize(node_list);
        return root;
    }