【LeetCode 297】二叉树的序列化与反序列化-蒲公英云

【LeetCode 297】二叉树的序列化与反序列化

Dear 丶 2022-11-30 01:42 247阅读 0赞

题目描述

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例:

你可以将以下二叉树：

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

提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。

解题思路

对于这道二叉树的题目，我们能想到的最直接的方式就是深度优先宾利和广度优先遍历，这里就分别用两种方式来解答。

深度优先遍历：

首先是序列化二叉树，可以定义一个遍历方法，先访问根节点，再访问左节点，最后访问右节点，将每个节点的值都存入数组，如果是null也要存入数组。
之后是反序列化二叉树，也就是将数组转化为二叉树，因为数组是二叉树先序遍历的结果，所以我们就可以遍历数组，然后按照根节点、左子树、右子树的顺序复原二叉树

使用深度优先遍历的方法的时间复杂度为O(n)，空间复杂度为O(n)。

广度优先遍历：

首先是序列化二叉树，广度优先遍历的遍历顺序是按照层级从上往下遍历（层序遍历），所以我们可以利用队列先进先出的特性，维持一个数组。先将根节点入队，再将左节点和右节点入队，递归即可。
之后是反序列化二叉树，我们可以从数组中取出第一个元素生成根节点，将根节点加入队列，循环队列，将根节点的左右子树分别加入队列，循环此操作，直至队列为空。其中队列中的节点用于后面遍历其左右子节点。

使用广度优先遍历的方法的时间复杂度为O(n)，空间复杂度为O(n)。

代码实现

深度优先遍历：

/** * Definition for a binary tree node. * 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 result = []
    function traverseNode(node){ 
        if(node === null){ 
            result.push(null)
        }else{ 
            result.push(node.val)
            traverseNode(node.left)
            traverseNode(node.right)
        }
    }
    traverseNode(root)
    return result
};
/** * Decodes your encoded data to tree. * * @param {string} data * @return {TreeNode} */
var deserialize = function(data) { 
    const len = data.length
    if(!len){ 
        return null
    }
    let i = 0
    function structure (){ 
        // 递归停止条件
        if(i >= len){ 
            return null
        }
        const val = data[i]
        i++
        if(val === null){ 
            return null
        }
        const node = new TreeNode(val)
        node.left = structure()
        node.right = structure()
        return node
    }
    return structure()
};
/** * Your functions will be called as such: * deserialize(serialize(root)); */

广度优先遍历：

/** * Definition for a binary tree node. * 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) { 
    if(!root){ 
        return []
    }
    const result = []
    const queue = []
    queue.push(root)
    let node ;
    while(queue.length){ 
        node = queue.shift()
        result.push(node ? node.val : null)
        if(node){ 
            queue.push(node.left)
            queue.push(node.right)
        }
    }
    return result
};
/** * Decodes your encoded data to tree. * * @param {string} data * @return {TreeNode} */
var deserialize = function(data) { 
    const len = data.length
    if(!len){ 
        return null
    }
    const root = new TreeNode(data.shift())
    const queue = [root]
    while(queue.length){ 
        // 取出将要遍历的节点
        const node = queue.shift()
        if(!data.length){ 
            break
        }
        // 还原左节点
        const leftVal = data.shift()
        if(leftVal === null){ 
            node.left = null
        }else{ 
            node.left = new TreeNode(leftVal)
            queue.push(node.left)
        }
        if(!data.length){ 
            break
        }
        // 还原右节点
        const rightVal = data.shift()
        if(rightVal === null){ 
            node.right = null
        }else{ 
            node.right = new TreeNode(rightVal)
            queue.push(node.right)
        }
    }
    return root
};
/** * Your functions will be called as such: * deserialize(serialize(root)); */