文章目录[隐藏]

• 题目-序列化和反序列化二叉树
• 要求
• Just Try
• 参考答案

序列化是指将一个特定的数据结构或者对象转换成一个字符序列可以存储在文件或者内存，或者通过网络传输，然后再另一个需要使用的环境中可以通过反序列化将这个字符序列转换成之前的数据结构或者对象。

给定一个二叉树，需要你把他序列化成一个字符串，然后在反序列化成二叉树。要求：

1. 序列化和反序列化的算法要求是无状态的纯函数，不能使用外部引用来存储数据。
2. 序列化成字符串，不能用 “转成json再序列化” 的方法

示例： 上图中的二叉树序列化成[12356]

Just Try

请你自动动手试一下：在线编程环境

想想有没有其他思路？

想想时间和空间复杂度，能否优化一下

真的做不到么？

let you think， think makes you happy!

看下这个文章：二叉树的常用算法

 

参考答案

下面给出了完整的代码和详细的注释，请仔细阅读哈

/** 节点类，代表一个节点
**  包含自身数据，左节点应用和又节点引用
**/
class Node {
  // 构造函数简单处理
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}
/** 二叉树类，代表一棵二叉树
**  包含一个根节点，然后是叶子节点
//          15 
//         /  \ 
//        10   13 
//       /     / \ 
//      7     22  25
//     / \    /    \
//    5   9  17     27
**/
class BinarySearchTree {
  // 构造函数默认初始化根节点
  constructor() {
    this.root = null;
  }
  // 插入节点
  insert(data) {
    var newNode = new Node(data);
    if (this.root == null) {
      this.root = newNode;
    }
    else {
      this.insertNode(this.root, newNode);
    }
  }
  // 插入节点，将小的数据放在左边节点，大的数据放在右边节点
  insertNode(node, newNode) {
    if (newNode.data < node.data) {
      if (node.left == null) {
        node.left = newNode;
      }
      else {
        this.insertNode(node.left, newNode);
      }
    }
    else {
      if (node.right == null) {
        node.right = newNode;
      }
      else {
        this.insertNode(node.right, newNode);
      }
    }
  }
  // 中序遍历，先左节点，后自身数据，最后右边节点
  inorder(node, arr) {
    if (node !== null) {
      this.inorder(node.left, arr )
      arr.push(node.data)
      // console.show(node.data,level-1)
      this.inorder(node.right, arr)
    }
  }
  // 先序遍历，先自身数据，后左节点，最后右边节点，
  preorder(node, arr) {
    if (node !== null) {
      arr.push(node.data)
      this.preorder(node.left, arr)
      this.preorder(node.right, arr)
    }
  }
  // 后序遍历，先左节点，后右边节点，最后自身数据
  postorder(node, arr) {
    if (node !== null) {
      this.preorder(node.left, arr)
      this.preorder(node.right, arr)
      arr.push(node.data)
    }
  }
  // 快速初始化一棵树
  restore(str){
    str.split(",").forEach(item=>{
      this.insert(+item)
    }
                          )
  }
}
function main() {
  // create an object for the BinarySearchTree 
  var BST = new BinarySearchTree();
  // Inserting nodes to the BinarySearchTree 
  BST.restore("15,10,7,5,9,13,25,22,17,27");
  //          15 
  //         /  \ 
  //        10   13 
  //       /     / \ 
  //      7     22  25
  //     / \    /    \
  //    5   9  17     27
  let arr = []
  BST.inorder(BST.root, arr)
  console.show(arr.join(","))
  
  // 可以看到先序遍历的结果和我们插入的数据是一样的，可以用这个做序列化和反序列化
  arr = []
  BST.preorder(BST.root, arr)
  console.show(arr.join(","))
  
  
  arr = []
  BST.postorder(BST.root, arr)
  console.show(arr.join(","))
}
main();