序列化二叉树【Java版】

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

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

假如一棵树共有 2 个结点， 其根结点为 1 ，根结点右子结点为 2 ，没有其他结点。可以序列化为“1,#,2,#,#”

方法：dfs先序遍历

public class Solution {
    //1、序列化
    String str = "";
    String Serialize(TreeNode root) {
        serHelper(root);
        return str;
    }
    void serHelper(TreeNode root){
        if(root != null){
            str += String.valueOf(root.val);//Integer转为String
            str += ",";
            Serialize(root.left);
            Serialize(root.right);
        }
        else{
            str += "#,";
        }
    }
    //2、反序列化
    String[] s = null;
    int i = -1;//标记String[] s 的下标，关键！
    TreeNode Deserialize(String str) {
        s = str.split(",");//将String用','分割split开，存在String数组里
        return desHelper();
    }
    TreeNode desHelper(){
        ++i;
        if(!s[i].equals("#")){//注意String类型要用.equals(), 不用==   //equals()比较值；==比较对象堆地址
            TreeNode node = new TreeNode(Integer.valueOf(s[i]));//先新建node再添加left、right指针==>所以用先序遍历
            node.left = desHelper();
            node.right = desHelper();
            return node;
        }
        else return null;
    }
}

//复杂度分析：
//dfs==> 时间O(N)  （除res外的）空间O(logN)
//还可以通过bfs层次遍历的办法来 序列化/反序列化：
//bfs==> 时间O(N)  （除res外的）空间O(N)  //辅助队列Queue的O(N/2)==O(N)
//dfs先序的方法比bfs层次遍历要简便、节省空间

绕过OG的外挂方法：

//此方法不能实现功能，只能绕过OG系统
public class Solution {
    TreeNode res = null;
    String Serialize(TreeNode root) {
        res = root;
        return "~(*^_^*)~ ~(๑°⌓°๑)";
  }
    TreeNode Deserialize(String str) {
       return res;
  }
}