首页 > 试题广场 >

序列化二叉树

[编程题]序列化二叉树

热度指数：486351 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。

二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过某种符号表示空节点（#）

二叉树的反序列化(Deserialize)是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

例如，可以根据层序遍历的方案序列化，如下图:

层序序列化(即用函数Serialize转化)如上的二叉树转为"{1,2,3,#,#,6,7}"，再能够调用反序列化(Deserialize)将"{1,2,3,#,#,6,7}"构造成如上的二叉树。

再举一个例子

层序序列化(即用函数Serialize转化)如上的二叉树转为"{5,4,#,3,#,2}"，再能够调用反序列化(Deserialize)将"{5,4,#,3,#,2}构造成如上的二叉树。

当然你也可以根据满二叉树结点位置的标号规律来序列化，还可以根据先序遍历和中序遍历的结果来序列化。不对序列化之后的字符串进行约束，所以欢迎各种奇思妙想。

数据范围：节点数 $n \le 100$ ，树上每个节点的值满足 $0 \le val \le 150$

要求：序列化和反序列化都是空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

示例1

输入

{1,2,3,#,#,6,7}

输出

{1,2,3,#,#,6,7}

说明

如题面图

示例2

输入

{8,6,10,5,7,9,11}

输出

{8,6,10,5,7,9,11}

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Javascript

哲学家L

function Serialize(root)
{
    return JSON.stringify(root)
}
function Deserialize(s)
{
    return JSON.parse(s)
}

发表于 2022-07-29 10:53:01 回复(2)

Javascript

一公升的眼泪

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}
function Serialize(pRoot)
{
    // 层序遍历
   if(pRoot === null){
       return "#";
   }
    const queue = [pRoot];
    let depth = 0;
    let res = [];
    while(queue.length){
        let len = queue.length;
        if(len > 0){
            depth++;
        }
        while(len--){
            let node = queue.shift();
            if(node.left !== null){
                queue.push(node.left);
            }
            if(node.right !== null){
                queue.push(node.right);
            }
        }
    }
    
    const queue2 = [pRoot];
    while(queue2.length && depth){
        let len = queue2.length;
        while(len--){
            let node = queue2.shift();
            if(node.val !== Infinity){
                res.push(node.val);
            }else{
                res.push("#");
            }
            if(node.left !== null){
                queue2.push(node.left);
            }else if(node.val !== Infinity){
                let newNode = new TreeNode(Infinity);
                queue2.push(newNode);
            }
            if(node.right !== null){
                queue2.push(node.right);
            }else if(node.val !== Infinity){
                let newNode = new TreeNode(Infinity);
                queue2.push(newNode);
            }
        }
        depth--;
    }
    return  res.join(",");
}
function Deserialize(s)
{
    // 根据字符串构造一棵树
    if(s === "#"){
        return null;
    }
    let res = s.split(",");
    let queue = [];
    let nodeVal = res.shift();
    let root = new TreeNode(nodeVal);
    queue.push(root);
    while(queue.length){
        let node = queue.shift();
        let len = 2;
        while(len-- && res.length){
            let val = res.shift();
            if(len === 1 && val !== "#"){
                let childNode1 = new TreeNode(val);
                node.left = childNode1;
                queue.push(childNode1);
            }
            if(len === 0 && val !== "#"){
                let childNode2 = new TreeNode(val);
                node.right = childNode2;
                queue.push(childNode2)
            }
        }
    }
    return root;
}
module.exports = {
    Serialize : Serialize,
    Deserialize : Deserialize
};

发表于 2022-07-15 11:00:37 回复(0)

Javascript

Jimmy0.0

非递归版本JavaScript 精简实现：

使用队列实现

/**
 *
 * @param {TreeNode} pRoot
 * @returns
 */
function Serialize(pRoot) {
    if (!pRoot) return "{}";
    let [resQueue, idx] = [[pRoot], 0];
    while (idx < resQueue.length)
        if (resQueue[idx++]) resQueue.push(resQueue[idx - 1].left, resQueue[idx - 1].right);
    const resStr = resQueue.reverse().slice(resQueue.findIndex(s=>s!==null)).reverse().map((s) => (s ? s.val : "#")).join(",");
    return `{${resStr}}`;
}

/**
 *
 * @param {string} s
 * @returns
 */
function Deserialize(s) {
    // write code here
    const arr = s.match(/\d+|#/g);
    if (!arr || arr[0] === "#") return null;
    const head = new TreeNode(arr[0]),queue = [head];
    for (let index = 1; index < arr.length; index += 2) {
        const node = queue.shift();
        if (arr[index] !== "#")
            queue.push((node.left = new TreeNode(arr[index])));
        if (index + 1 < arr.length && arr[index + 1] !== "#")
            queue.push((node.right = new TreeNode(arr[index + 1])));
    }
    return head;
}

发表于 2022-04-04 12:27:04 回复(0)

JavaScript

别卷啦！

序列化：将节点值存入数组中空节点使用特殊标记存入数组；

反序列化：从数组中获取元素 number类型则生成节点为特殊节点则为空节点；

var arr=[];
function Serialize(pRoot)
{
    // write code here
    if(pRoot==null){
        arr.push('#')
        return;
    } 
    arr.push(pRoot.val);
    Serialize(pRoot.left)
    Serialize(pRoot.right)
}
function Deserialize(s)
{
    // write code here
    if(arr==null){
        return null;
    }

    if(arr.length<1){
        return null;
    }
    var root=null;
    var temp=arr.shift();
    if(typeof temp=='number'){
        root=new TreeNode(temp);
        root.left=Deserialize(arr);
        root.right=Deserialize(arr);
    }
    return root;
}

发表于 2021-07-02 20:55:57 回复(0)

JavaScript

牛客749758891号

懒得解析了,本来打算按层放数组里转json的,后来想了一下,我为啥不直接转json呢

function Serialize(pRoot)
{
return JSON.stringify(pRoot)
}
function Deserialize(s)
{
return JSON.parse(s)
}

编辑于 2020-10-21 22:56:10 回复(0)

JavaScript

莫得名字的

深度优先遍历序列化存字符串
递归构建二叉树

function TreeNode(x) {
  this.val = x;
  this.left = null;
  this.right = null;
}
function Serialize(pRoot)
{
  // write code here
  // 深度优先遍历，栈
  let stack = [];
  let res = '';
  if (!pRoot) {
    return '#';
  }
  stack.push(pRoot);

  while (stack.length) {
    let node = stack.pop();

    // 节点为空（null）
    if (node === null) {
      res += '#,';
    } else if (node.val) {
      res += node.val + ',';
    }

    node && stack.push(node.right);
    node && stack.push(node.left);
  }
  // console.log(res);
  return res;
}
function Deserialize(s)
{
  // write code here
  if (s === '#') {
    return;
  }
  let arr = s.split(',');
  // 删去最后一个空值
  arr.splice(arr.length-1, 1);
  // console.log(arr);

  let root = reConstructTree(arr);
  return root;  
}

function reConstructTree (arr) {
  let val = arr.shift();
  let node;

  if (val !== '#') {
    val = parseInt(val);
    node = new TreeNode(val);
  } else if (val === '#') {
    return null;
  }

  node.left = reConstructTree(arr);
  node.right = reConstructTree(arr);

  return node;
}


let node1 = new TreeNode(1);
let node2 = new TreeNode(2);
let node3 = new TreeNode(3);
let node4 = new TreeNode(4);
let node5 = new TreeNode(5);
let node6 = new TreeNode(6);

node1.left = node2;
node1.right = node4;

node2.right = node3;

node4.left = node5;
node4.right = node6;

Serialize(node1);
Deserialize('1,2,#,3,#,#,4,5,#,#,6,#,#,');

发表于 2019-08-15 11:05:33 回复(0)

JavaScript

Dobility

一种偷懒的写法

function Serialize(pRoot) {
    return JSON.stringify(pRoot)
}
function Deserialize(s) {
    return JSON.parse(s)
}

编辑于 2019-04-16 20:12:07 回复(0)

JavaScript

不去大厂不换昵称

若一颗二叉树是不完全的，我们至少需要两个遍历才能将它重建（像题目重建二叉树一样）

但是这种方式仍然有一定的局限性，比如二叉树中不能出现重复节点。

如果二叉树是一颗完全二叉树，我们只需要知道前序遍历即可将它重建。

因此在序列化时二叉树时，可以将空节点使用特殊符号存储起来，这样就可以模拟一棵完全二叉树的前序遍历

在重建二叉树时，当遇到特殊符号当空节点进行处理

    function Serialize(pRoot, arr = []) {
      if (!pRoot) {
        arr.push('#');
      } else {
        arr.push(pRoot.val);
        Serialize(pRoot.left, arr)
        Serialize(pRoot.right, arr)
      }
      return arr.join(',');
    }
    function Deserialize(s) {
      if (!s) {
        return null;
      }
      return deserialize(s.split(','));
    }

    function deserialize(arr) {
      let node = null;
      const current = arr.shift();
      if (current !== '#') {
        node = { val: current }
        node.left = deserialize(arr);
        node.right = deserialize(arr);
      }
      return node;
    }

发表于 2019-04-03 22:10:10 回复(0)

JavaScript

汕大小吴

JS版本来啦

首先拿到题目时候，我先想到的是什么是序列化二叉树？序列化主要就是在前后端交互时候需要转换下，毕竟网络传输的是流式数据（二进制或者文本），而不是对象。

所以序列化二叉树就是转化成字符串。

之前解决重建二叉树问题时候，我们可以知道，两个遍历序列就可以确定一颗二叉树。（比如前序遍历序列和中序遍历序列）。

受此启发，序列化时候我们可以生成一个前序遍历序列和一个中序遍历序列，在反序列化时通过这两个序列重构出原二叉树。

但是当我们细细想下，这个思路有两个个缺点就是：

1.如果二叉树有数值重复的节点，那么必须区分谁是前序遍历序列，谁是后序遍历序列。

2.只有当两个序列所有数据读出后才能开始反序列化。

因此我们可以想，既然是可以边读，边构建二叉树，你是不是想到了自己平时如何构建二叉树的？

我们可以通过深度遍历或者广度遍历序列都行，当然我们最终选择了深度优先遍历，毕竟可以不用额外的空间。

此外还有个技巧就是为了更好地知道遍历某个子树的结束，也就是当我们遍历到null时，我们需要用换位符（比如$）代表，方便反序列化。

此外，我尝试过用字符串做发现不好做，然后转变了下思路，用数组来模拟流，发现就好做了很多。

let arr = [];
function Serialize(pRoot)
{
    // write code here
    if(pRoot==null){
        arr.push('a');
    }else{
        arr.push(pRoot.val);
        Serialize(pRoot.left);
        Serialize(pRoot.right);
    }
        
}
function Deserialize(s)
{
    // write code here
    let node = null;
    if(arr.length<1){
        return null;
    }
    let number = arr.shift();
    if(typeof number == 'number'){
        node = new TreeNode(number);
        node.left = Deserialize(arr);
        node.right = Deserialize(arr);
    }
    return node;
}

发表于 2018-08-30 01:14:28 回复(0)