前言

有一顆二叉樹，將它轉(zhuǎn)換成特定規(guī)則的字符串就稱之為序列化，將序列化后的字符串按照序列化時(shí)的規(guī)則還原成二叉樹就稱之為反序列化。

那么如何實(shí)現(xiàn)二叉樹與字符串之間的相互轉(zhuǎn)換呢？本文就跟大家分享下這個(gè)問題的解決方案，歡迎各位感興趣的開發(fā)者閱讀本文。

實(shí)現(xiàn)思路

在文章重建二叉樹中，我們學(xué)會(huì)了利用前序遍歷序列和中序遍歷序列將一個(gè)字符串構(gòu)建成一顆二叉樹。這個(gè)思路有兩個(gè)缺點(diǎn)：

• 二叉樹中不能有數(shù)值重復(fù)的節(jié)點(diǎn)
• 只有當(dāng)兩個(gè)序列中所有的數(shù)據(jù)都讀出來后才能開始反序列化（如果兩個(gè)序列中的數(shù)據(jù)都是從一個(gè)流里讀出來的，那么就需要等待比教長(zhǎng)的時(shí)間）

其實(shí)，當(dāng)我們用前序遍歷來讀取二叉樹時(shí)，得到的序列是從根節(jié)點(diǎn)開始的，那么反序列化時(shí)在根節(jié)點(diǎn)讀取出來之后就可以開始了。當(dāng)我們?cè)谛蛄谢臅r(shí)候可能會(huì)遇到空節(jié)點(diǎn)，我們用一個(gè)特殊的字符來標(biāo)記它（例如"$"）。節(jié)點(diǎn)值之間的連接也需要用特殊字符標(biāo)記（例如","）。

序列化的規(guī)則捋清楚后，我們舉個(gè)例子來驗(yàn)證下是否可行，如下所示（一顆二叉樹）：

根據(jù)上面定義的規(guī)則，我們使用前序遍歷得到的序列為：1,2,4,$,$,$,3,5,$,$,6,$,$。

經(jīng)過驗(yàn)證，上述方法成功的實(shí)現(xiàn)了樹的序列化。接下來我們以字符串1,2,4,$,$,$,3,5,$,$,6,$,$為例分析如何反序列化二叉樹。

第一個(gè)讀出的數(shù)字是1。由于前序遍歷是從根節(jié)點(diǎn)開始的，這是根節(jié)點(diǎn)的值。緊接著讀出的數(shù)字是2，根據(jù)前序遍歷的規(guī)則，這是根節(jié)點(diǎn)的左子節(jié)點(diǎn)的值。同樣的，接下來的數(shù)字4是值為2的節(jié)點(diǎn)的左子節(jié)點(diǎn)。

接著從序列化字符串里讀出兩個(gè)字符"$"，這表明節(jié)點(diǎn)4的左、右子節(jié)點(diǎn)均為空，因此它是一個(gè)葉節(jié)點(diǎn)。

接下來返回至節(jié)點(diǎn)2，重建它的右子節(jié)點(diǎn)。繼續(xù)讀取字符，下一個(gè)字符是"$"，這表明節(jié)點(diǎn)2的右子節(jié)點(diǎn)為空。這個(gè)節(jié)點(diǎn)的左、右子樹都已經(jīng)構(gòu)建完畢。

接下來返回至根節(jié)點(diǎn)，反序列化根節(jié)點(diǎn)的右子樹。

下一個(gè)序列化字符串中讀取出來的數(shù)字是3，因此根節(jié)點(diǎn)的右子樹的值為3。它的左子節(jié)點(diǎn)是一個(gè)值為5的葉節(jié)點(diǎn)，因?yàn)榻酉聛淼娜齻€(gè)字符是"5,$,$"。

同樣，它的右子節(jié)點(diǎn)是值為6的葉節(jié)點(diǎn)，因?yàn)樽詈?個(gè)字符是"6,$,$"。

字符串中的所有字符已讀取完畢，序列化流程結(jié)束，樹也完成重建，如下圖所示（去掉了分析思路時(shí)所畫的輔助線）

實(shí)現(xiàn)代碼

經(jīng)過前面的分析，我們已經(jīng)得到了完整的思路，接下來我們來看下代碼的實(shí)現(xiàn)。

序列化二叉樹

我們利用前序遍歷即可完成二叉樹的序列化。

  public serialize(root: BinaryTreeNode | null): string {
    // 空節(jié)點(diǎn)用$表示
    if (root == null) return "$";
    const result: serializeNode = { nodeVal: "" };
    this.serializeFn(root, result);
    // 末尾會(huì)有多余的分隔符，將其去除
    return result.nodeVal.substring(0, result.nodeVal.length - 1);
  }


  /**
   * 處理樹序列化的實(shí)現(xiàn)函數(shù)
   * @param root 樹的根節(jié)點(diǎn)
   * @param strObj 序列化后的節(jié)點(diǎn)對(duì)象
   * @private
   */
  private serializeFn(
    root: BinaryTreeNode | null | undefined,
    strObj: serializeNode
  ) {
    if (root == null) {
      strObj.nodeVal += "$,";
      return;
    }
    strObj.nodeVal += root.key + ",";
    this.serializeFn(root.left, strObj);
    this.serializeFn(root.right, strObj);
  }

反序列化

我們序列化的時(shí)候用的前序遍歷，同樣的在反序列化的時(shí)候也要使用前序遍歷。反序列的時(shí)候稍微麻煩些，需要先把字符串中的每個(gè)字符放到數(shù)組中。隨后再按照我們前面的分析：

• 定義一個(gè)全局變量across用來表示當(dāng)前讀取到了第幾個(gè)字符（已走步長(zhǎng)）
• 遞歸執(zhí)行構(gòu)建函數(shù)時(shí)，已走步長(zhǎng)先自增。

• 根節(jié)點(diǎn)的左子樹一定是緊根其后的字符，所以從index+1位置開始繼續(xù)執(zhí)行遞歸函數(shù)直至遇到"$"字符為止
• 根節(jié)點(diǎn)的右子樹一定是緊根在它左子樹之后的字符，所以從across位置開始繼續(xù)執(zhí)行遞歸函數(shù)直至遇到"$"字符為止
• 構(gòu)建函數(shù)接受兩個(gè)參數(shù)：字符數(shù)組、當(dāng)前讀取的字符索引
• 從字符數(shù)組中讀取當(dāng)前字符索引位置的值，構(gòu)建根節(jié)點(diǎn)
• 左、右子樹都構(gòu)建完畢后，將構(gòu)建好的根節(jié)點(diǎn)返回就得到了一顆完整的樹

  /**
   * 反序列化二叉樹
   * @param treeStr
   */
  public deserialize(treeStr: string): BinaryTreeNode | null {
    if (treeStr === "$") {
      return null;
    }
    return this.deserializeFn(treeStr);
  }

  /**
   * 處理樹的反序列化實(shí)現(xiàn)函數(shù)
   * @param nodeStrVal 反序列化后的樹節(jié)點(diǎn)字符串
   * @private
   */
  private deserializeFn(nodeStrVal: string) {
    // 讀取字符串的每一個(gè)字符，將其轉(zhuǎn)換為數(shù)組
    const strArr: Array<string> = [];
    let readIndex = 0;
    while (readIndex < nodeStrVal.length) {
      if (nodeStrVal.charAt(readIndex) !== ",") {
        strArr.push(nodeStrVal.charAt(readIndex));
      }
      readIndex++;
    }
    // 反序列化二叉樹
    return this.buildTree(strArr, 0);
  }

  /**
   * 將字符串?dāng)?shù)組序列化為二叉樹
   * @param str 字符串?dāng)?shù)組
   * @param index 起始索引
   * @private
   */
  private buildTree(str: Array<string>, index: number) {
    this.across++;
    // 處理空節(jié)點(diǎn)（遞歸的基線條件）
    if (str[index] === "$") return null;
    // 構(gòu)造樹節(jié)點(diǎn)
    const treeNode: BinaryTreeNode = { key: parseInt(str[index]) };
    // 當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)一定為它的左子樹
    treeNode.left = this.buildTree(str, index + 1);
    // 左子樹遇到基線條件后，右子樹的索引就為已走步長(zhǎng)
    treeNode.right = this.buildTree(str, this.across);
    return treeNode;
  }

測(cè)試用例

我們用文章開頭所列舉的例子來驗(yàn)證下上述代碼能否正確的解決問題。

const rootNode: BinaryTreeNode = {
  key: 1,
  left: {
    key: 2,
    left: {
      key: 4
    }
  },
  right: {
    key: 3,
    left: {
      key: 5
    },
    right: {
      key: 6
    }
  }
};

const serializedBinaryTree = new SerializedBinaryTree();
const treeStr = serializedBinaryTree.serialize(rootNode);
console.log("序列化后的字符串", treeStr);
const result = serializedBinaryTree.deserialize(treeStr);
console.log("反序列化后的樹", result);

執(zhí)行結(jié)果如下所示。

示例代碼

本文用到的代碼完整版請(qǐng)移步：

• SerializedBinaryTree.ts
• SerializedBinaryTree-test.ts