function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} 
function Serialize(r)
{
    if(r === null)
        return "#!";
    var res = "";
    var s = [];
    s.push(r);
    while(s.length !== 0){
        var cur = s.pop();
        res += (cur === null) ? "#" : cur.val;
        res += "!";
        if(cur !== null) {
            s.push(cur.right);
            s.push(cur.left);
        }
    }
    return res;
}
function Deserialize(s)
{
    if(s === "")
        return null;
    var arr = s.split("!");
    return step(arr);
}
function step(arr) {
    var cur = arr.shift();
    if(cur === "#")
        return null;
    var node = new TreeNode(cur);
    node.left = step(arr);
    node.right = step(arr);
    return node;
}