297.二叉树的序列化与反序列化.hard

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

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function (root) {
    const res = levelOrder(root)
    // console.log(res)
    return res.join(',')
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function (data) {
    if(data === '') {
        return null
    }
    const dataArr = data.split(',')
    // console.log(data)
    const root = levelOrderToTree(dataArr)
    return root
};

/**
 * 前序遍历，中左右
 * @param {TreeNode} root 
 * @param {[]number} res 
 */
function preorder(root, res) {
    res = res || []
    if (!root) {
        res.push('NULL')
        return res
    }

    res.push(root.val)
    preorder(root.left, res)
    preorder(root.right, res)

    return res
}

/**
 * 前序遍历转成树，再按前序遍历的顺序将节点恢复即可
 * @param {[]number} arr 
 */
function preorderToTree(arr) {
    let val = arr.shift()
    if (val === 'NULL') {
        return null
    }
    let root = new TreeNode(val) // 中
    root.left = preorderToTree(arr) // 左
    root.right = preorderToTree(arr) // 右

    return root
}

/**
 * 中序遍历，左中右
 * @param {TreeNode} root 
 * @param {[]number} res 
 */
function inorder(root, res) {
    res = res || []
    if (!root) {
        res.push('NULL')
        return res
    }
    preorder(root.left, res)
    res.push(root.val)
    preorder(root.right, res)

    return res
}

/**
 * 层序遍历
 * @param {TreeNode} root 
 */
function levelOrder(root) {
    if (!root) {
        return []
    }
    let queue = []
    queue.push(root) // 第一层

    let res = []
    while (queue.length) {
        let len = queue.length // 每一层的节点数量
        for (let i = 0; i < len; i++) {
            let node = queue.shift()
            res.push(node ? node.val : 'NULL')

            if (node) {
                queue.push(node.left)
                queue.push(node.right)
            }
        }
    }

    return res
}

/**
 * 层序遍历转树
 * @param {[]number} arr 
 */
function levelOrderToTree(arr) {
    let queue = []
    let rootVal = arr.shift() // 根节点
    let root = new TreeNode(rootVal)
    queue.push(root)
    while (queue.length) {
        let node = queue.shift()
        let left = arr.shift() // 左节点
        let right = arr.shift() // 右节点

        if (left === 'NULL') {
            node.left = null
        } else {
            let leftNode = new TreeNode(left)
            node.left = leftNode
            queue.push(leftNode) // 加入队列
        }

        if (right === 'NULL') {
            node.right = null
        } else {
            let rightNode = new TreeNode(right)
            node.right = rightNode
            queue.push(rightNode) // 加入队列
        }
    }
    return root
}

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */