【基础篇 - Day 17】 2020-11-17 - Offer 37. 序列化二叉树（03. 树）

题目描述

入选理由

1. 题目官方难度是 hard，做了几天容易的题了，该找点刺激了。
2. 帮助你理解树的遍历和构建，合二为一，岂不美哉？

题目描述

请实现两个函数，分别用来序列化和反序列化二叉树。

示例:

你可以将以下二叉树：

    1
   / \
  2   3
     / \
    4   5

序列化为 "[1,2,3,null,null,4,5]"

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处

我的回答

解法一

时空复杂度

时间复杂度：O(n)

空间复杂度: O(n)

bfs 序列化比较简单，层序遍历一遍，转成字符串

反序列化的话 同样要维护一个栈，不是 null 的节点都可以进栈，因为每个节点都有两个对应数组值，每次出栈即加二

var serialize = function (root) {
    if (!root) return []
    let queue = [root]
    const res = []
    while (queue.length) {
        let curr = queue.shift()
        if (curr) {
            queue.push(curr.left)
            queue.push(curr.right)
            res.push(curr.val)
        } else {
            res.push('null')
        }
    }
    return res.join()
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function (data) {
    if (typeof data == 'object') return null
    const arr = data.split(',')
    let root = new TreeNode(arr[0])
    let queue = [root]
    let pointer = 1
    while (pointer < arr.length) {
        let curr = queue.shift()

        const leftVal = arr[pointer]
        const rightVal = arr[pointer + 1]
        // console.log(leftVal, rightVal, curr)
        if (leftVal != 'null') {
            const left = new TreeNode(leftVal)
            curr.left = left
            queue.push(left)
        }
        if (rightVal != 'null') {
            const right = new TreeNode(rightVal)
            curr.right = right
            queue.push(right)
        }
        pointer += 2
    }
    // console.log(root)
    return root
};

解法二

时空复杂度

时间复杂度：O(n)

空间复杂度: O(n)

https://github.com/leetcode-pp/91alg-2/issues/43#issuecomment-729347966

参考回答

• 官方题解 (opens new window)