剑指offer-61：序列化二叉树

题目：请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。
序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。
反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

     1
   2   3
  4 5 6 7
序列化之后的结果为：1!2!4!#!#!5!#!#!3!6!#!#!7!#!#!

思路：
1:这道题在内部的执行是：给定一个树，然后执行第一个序列化函数，再执行第二个反序列化函数，对比原来给的树，看是否相等。
2：序列化我通过先序遍历的思想，外部定义一个公共arr数组，如果结点为空，增加元素'#!'，如果不空，则增加 root.val(结点的值)+'!',然后对左节点和右节点进行深度先序遍历
3：反序列化，取出公共arr数组中的第一个元素，通过这个元素创造一个新结点，然后往这个结点的左右子树上挂载结点，在挂载之前要先判断这个元素是否为空，空的标志是'#!'，所以先进行判断，如果不等，则挂载，如果相等，那么直接进行else循环返回一个null结点。

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}
let arr = []
function Serialize(pRoot)
{
    // write code here
    if(!pRoot){
        arr.push('#!')
        return 
    }
    arr.push(pRoot.val+'!')
    Serialize(pRoot.left)
    Serialize(pRoot.right)
}
function Deserialize(s)
{
    // write code here
    if(!arr) return null
    let temp = arr.shift()
    if(temp !== '#!'){
        temp = temp.split('!')[0]
        var node = new TreeNode(temp)
        node.left = Deserialize(arr)
        node.right = Deserialize(arr)
    }else{
        return null
    }
    return node
}