SOURCE

// 你能否对二叉树进行序列化和反序列化？就像JSON.stringify() 和 JSON.parse() 所做的那样。

// 比如来自 91. 反转二叉树的二叉树。
// 1
// 2 3
// 4 5
// 6 7 8
//    9
// BFE.dev 会将其序列化为[1,2,3,4,null,null,5,6,7,8,null,null,null,null,9]。

// 但是当然还有其他的序列化方法，任何方法都OK，只要你的deserialize() 和 serialize() 可以成对工作。

// 你的代码会像这样被测试。

// const tree1 = ...
// expect(typeof serialize(tree1)).toBe('string')
// const tree2 = deserialize(serialize(tree1)) 
// expect(isIdentical(tree1, tree2)).toBe(true)
// 本体中的二叉树的节点值都是整数。


class Node {
    constructor(val, left = null, right = null) {
        this.value = val;
        this.left = left;
        this.right = right;
    }
};

/**
 * @param {Node} root
 * @return {string}
 */
function serialize(root) {
    if (!root) return '';
    const queue = [root];
    const arr = [];

    while (queue.length) {
        const node = queue.shift();

        if (node) {
            arr.push(node.value);
            queue.push(node.left);
            queue.push(node.right);
        } else {
            arr.push(null);
        };
    };

    return JSON.stringify(arr);
}

/**
 * @param {string} str
 * @return {Node}
 */
function deserialize(str) {
    // your code here
    if (!str) return null;
    const arr = JSON.parse(str);

    if (arr.length === 0) return null;

    const root = new Node(arr[0]);

    const queue = [root];
    let index = 1;

    while (queue.length > 0 && index < arr.length) {
        const cur = queue.shift();

        const leftVal = arr[index];

        if (leftVal !== null) {
            cur.left = new Node(leftVal);
            queue.push(cur.left);
        }

        const righVal = arr[index];

        if (righVal !== null) {
            cur.right = new Node(righVal);
            queue.push(cur.right);
        };

        index++;
    };

    return root;
};

// 1
// 2 3
// 4 5
// 6 7 8
//    9

const root = new Node(1,
    new Node(2,
        new Node(4,
            new Node(6, null, null),
            new Node(7, null,
                new Node(9, null, null)
            ),
            null,
        )),
    new Node(3, null,
        new Node(5,
            new Node(8), null))
);

console.log('test', serialize(root));