序列化二叉树
题目描述
示例
代码
代码1 层次遍历,序列化和反序列化
js
/*
序列化函数:二叉树转字符串
使用层次遍历将二叉树转换为字符串
空节点使用 # 占位
*/
function Serialize(pRoot)
{
if(!pRoot) return '' // 如果是空树,返回空字符串
// 层次遍历序列化为字符串
let q = [] // 使用js的数组模拟队列
q.push(pRoot) // 入队
let placeHolder = new TreeNode('#') // 空节点的占位符
let result = [] // 最终返回的结果,记得转换为字符串
// 开始层次遍历
while( q.length > 0 ){
let current = q.shift() // 使用shift模拟出队
// 如果是占位符,就不继续找他的下一层了
if(current !== placeHolder){
// 下一层入队,如果没有左右节点,使用个占位符
q.push( current.left ? current.left : placeHolder)
q.push( current.right ? current.right : placeHolder)
}
// 将每一层的节点,依次塞进结果数组中
result.push(current.val)
}
// 返回的结果是一串字符串
return result.join()
}
/*
反序列化函数: 字符串转二叉树
层次遍历的字符串 还原为一个树,返回它的头节点
还按照层次遍历的思路来解
*/
function Deserialize(s)
{
if(!s) return null // 如果是空字符串,返回空节点
let arr = s.split(',') // 字符串转为数组
let q = [] // 使用数组模拟队列,一层一层的还原
let root = new TreeNode( +arr.shift() ) // 根节点
q.push(root) // 入队
// 开始一层一层的还原
while( q.length > 0 ){
let current = q.shift() // 出队
// 拼接左节点
let leftVal = arr.shift()
if(leftVal === '#'){
current.left = null
// 空节点就不用继续找了,无需入队
}else {
let leftNode = new TreeNode(+leftVal)
current.left = leftNode
// 入队
q.push(leftNode)
}
// 拼接右节点
let rightVal = arr.shift()
if(rightVal === '#'){
current.right = null
// 空节点就不用继续找了,无需入队
}else {
let rightNode = new TreeNode(+rightVal)
current.right = rightNode
// 入队
q.push(rightNode)
}
}
return root // 返回最终拼接好的根
}
时间复杂度O(n)
空间复杂度O(n)
代码2 先序遍历,序列化和反序列化
js
/*
先序遍历序列化
1. 为null的地方输出个 #
*/
function Serialize(pRoot)
{
if(!pRoot) return '' // 如果空节点,返回一个空字符串
let result = [] // 先序遍历的结果存到此处,值为null的保存为 #
// 先序遍历存结果
preOrder(pRoot)
return result.toString() // 返回序列化后的字符串
// 先序遍历 根左右
function preOrder(pRoot){
// 出口
if(pRoot === null){
result.push('#')
return
}
result.push(pRoot.val)
preOrder(pRoot.left)
preOrder(pRoot.right)
}
}
/*
先序遍历字符串反序列化为树
返回根节点
*/
function Deserialize(s)
{
if(!s) return null // 如果是空字符串,返回空节点
let arr = s.split(',') // 字符串转为数组
// 先序遍历重建二叉树
let root = preOrder(arr)
return root
// 先序遍历 数组转为二叉树,返回头结点
function preOrder(arr) {
let val = arr.shift() // shift方法 原数组的长度会减一,返回删除的头结点
// 出口
if(val === '#') {
return null
} else {
let current = new TreeNode( +val )
current.left = preOrder(arr)
current.right = preOrder(arr)
return current
}
}
}
时间复杂度O(n)
空间复杂度O(n)