序列化二叉树

题目描述

示例

代码

代码1 层次遍历，序列化和反序列化

/*
序列化函数：二叉树转字符串

使用层次遍历将二叉树转换为字符串
空节点使用 # 占位
*/
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 先序遍历，序列化和反序列化

/*
先序遍历序列化
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)

题目来源

JZ37 序列化二叉树