二叉树的序列化与反序列化|博客系列 | 前端进阶之旅

# 二叉树的序列化与反序列化

# 题目描述

请实现两个函数，分别用来序列化和反序列化二叉树

例如给定的一棵树的结构为：

要求返回序列化为1,2,#,#,3,4,#,#,5,#,#

# 解题思路

序列化思路

判断节点的值是否存在，若是不存在则需要用一个特殊符号来代替，如#符号；
序列化实际就是将二叉树进行前序遍历

反序列化思路

判断值为#的项，将其转换为null;
输入的数组为二叉树的前序遍历，利用这一特性进行左右子树的赋值

# coding

class Node {
    constructor(value = 0, left = null, right = null) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}
/*
* 序列化二叉树
* param {Tree} tree 二叉树
* param {Array} arr 序列化之后的数组
* return {String} 返回序列化之后字符串
*/
function serialize(node, arr = []) {
    if (!node) { // 判断该节点有没有，没有则用特殊符号 # 代替
        arr.push('#');
    } else {
        arr.push(node.value); // 当前节点的值
        serialize(node.left, arr) // 分别遍历左右子树
        serialize(node.right, arr)
    }
    return arr.join(','); // 将返回的数组进行逗号连接（若想返回数组则不用.join(',')）
}
/*
* 反序列化二叉树，通过字符串
* param {String} str 序列化之后的字符串
*/
function DeSerializeByStr (str) {
    if (!str) return null;
    return DeserializeByArr(str.split(','))
}
/*
* 反序列化二叉树，通过数组
* param {Array} arr 序列化之后的数组
*/
function deSerializeByStr (str) {
  if (!str) return null;
  let arr = str.split(',');
  let deSerializeByArr = function (arr) {
    let currentNode = arr.shift(); // 第一项为根
    if (currentNode === '#') {
      return null;
    } else {
      let node = new Node(currentNode);
      node.left = deSerializeByArr(arr);
      node.right = deSerializeByArr(arr);
      return node;
    }
  }
  return deSerializeByArr(arr);
}
const tree = new Node(1, new