【基础篇 - 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]
    let result = []
    while (queue.length) {
        let curr = queue.shift()
        if (curr) {
            queue.push(curr.left)
            queue.push(curr.right)
            result.push(curr.val)
        } else {
            result.push('null')
        }
    }
    return result.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 point = 1
    let queue = [root]
    while (point < arr.length) {
        let curr = queue.shift()
        const left = arr[point]
        if (left !== "null") {
            curr.left = new TreeNode(left)
            queue.push(curr.left)
        }
 
        const right = arr[point + 1]
        if (right !== "null") {
            curr.right = new TreeNode(right)
            queue.push(curr.right)
        }
        point += 2
    }
    return root
};

解法二

时空复杂度

时间复杂度：O(n)

空间复杂度: O(n)

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

参考回答

• 官方题解