题解 | #序列化二叉树# JS Node 实现

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}

function Serialize(pRoot) {
    if (pRoot === null) return "#";

    var res = [];
    SerializeFunc(pRoot, res);
    return res.join("");
}

function SerializeFunc(root, str) {
    if (root === null) {
        str.push('#');
        return;
    }

    str.push(root.val + '!');
    SerializeFunc(root.left, str);
    SerializeFunc(root.right, str);
}

function Deserialize(s) {
    if (s === "#") return null;
    var index = { val: 0 }; // 使用对象包装index，以在递归中共享引用

    return DeserializeFunc(s, index);
}

function DeserializeFunc(s, index) {
    if (index.val >= s.length) {
        return null;
    }

    var c = s.charAt(index.val);
    if (c === '#') {
        index.val++;
        return null;
    }

    var isNegative = false;
    if (c === '-') {
        isNegative = true;
        index.val++;
    }

    var val = 0;
    while (index.val < s.length && s.charAt(index.val) !== '!') {
        val = val * 10 + parseInt(s.charAt(index.val));
        index.val++;
    }

    if (isNegative) {
        val *= -1;
    }

    var root = new TreeNode(val);

    if (index.val < s.length) {
        index.val++; // 跳过 '!'
        root.left = DeserializeFunc(s, index);
        root.right = DeserializeFunc(s, index);
    }

    return root;
}

module.exports = {
    Serialize: Serialize,
    Deserialize: Deserialize
};