JSON 的運用非常廣泛，比如我們經常將變成語言中的結構體序列化成 JSON 字串，存入快取或者透過網路傳送給遠端服務，消費者接受 JSON 字串然後進行反序列化，就可以得到原始資料了。這就是「序列化」和「反序列化」的目的，以某種固定格式組織字串，使得資料可以獨立於程式語言。

那麼假設現在有一棵用 Java 實現的二叉樹，我想把它序列化字串，然後用 C++ 讀取這棵並還原這棵二叉樹的結構，怎麼辦？這就需要對二叉樹進行「序列化」和「反序列化」了。

一、題目描述

「二叉樹的序列化與反序列化」就是給你輸入一棵二叉樹的根節點 root，要求你實現如下一個類：

public class Codec {    // 把一棵二叉樹序列化成字串    public String serialize(TreeNode root) {}    // 把字串反序列化成二叉樹    public TreeNode deserialize(String data) {}}

我們可以用 serialize 方法將二叉樹序列化成字串，用 deserialize 方法將序列化的字串反序列化成二叉樹，至於以什麼格式序列化和反序列化，這個完全由你決定。

比如說輸入如下這樣一棵二叉樹：

serialize 方法也許會把它序列化成字串 2,1,#,6,3,#,#，其中 # 表示 null 指標，那麼把這個字串再輸入 deserialize 方法，依然可以還原出這棵二叉樹。也就是說，這兩個方法會成對兒使用，你只要保證他倆能夠自洽就行了。

想象一下，二叉樹結該是一個二維平面內的結構，而序列化出來的字串是一個線性的一維結構。所謂的序列化不過就是把結構化的資料「打平」，其實就是在考察二叉樹的遍歷方式。

二叉樹的遍歷方式有哪些？遞迴遍歷方式有前序遍歷，中序遍歷，後序遍歷；迭代方式一般是層級遍歷。本文就把這些方式都嘗試一遍，來實現 serialize 方法和 deserialize 方法。

二、前序遍歷解法

前文 學習資料結構和演算法的框架思維 說過了二叉樹的幾種遍歷方式，前序遍歷框架如下：

void traverse(TreeNode root) {    if (root == null) return;    // 前序遍歷的程式碼​    traverse(root.left);    traverse(root.right);}

真的很簡單，在遞迴遍歷兩棵子樹之前寫的程式碼就是前序遍歷程式碼，那麼請你看一看如下偽碼：

LinkedList<Integer> res;void traverse(TreeNode root) {    if (root == null) {        // 暫且用數字 -1 代表空指標 null        res.addLast(-1);        return;    }​    /****** 前序遍歷位置 ******/    res.addLast(root.val);    /***********************/​    traverse(root.left);    traverse(root.right);}

呼叫 traverse 函式之後，你是否可以立即想出這個 res 列表中元素的順序是怎樣的？比如如下二叉樹（# 代表空指標 null），可以直觀看出前序遍歷做的事情：

那麼 res = [1,2,-1,4,-1,-1,3,-1,-1]，這就是將二叉樹「打平」到了一個列表中，其中 -1 代表 null。

那麼，將二叉樹打平到一個字串中也是完全一樣的：

// 代表分隔符的字元String SEP = ",";// 代表 null 空指標的字元String NULL = "#";// 用於拼接字串StringBuilder sb = new StringBuilder();​/* 將二叉樹打平為字串 */void traverse(TreeNode root, StringBuilder sb) {    if (root == null) {        sb.append(NULL).append(SEP);        return;    }​    /****** 前序遍歷位置 ******/    sb.append(root.val).append(SEP);    /***********************/​    traverse(root.left, sb);    traverse(root.right, sb);}

StringBuilder 可以用於高效拼接字串，所以也可以認為是一個列表，用 , 作為分隔符，用 # 表示空指標 null，呼叫完 traverse 函式後，StringBuilder 中的字串應該是 1,2,#,4,#,#,3,#,#,。

至此，我們已經可以寫出序列化函式 serialize 的程式碼了：

String SEP = ",";String NULL = "#";​/* 主函式，將二叉樹序列化為字串 */String serialize(TreeNode root) {    StringBuilder sb = new StringBuilder();    serialize(root, sb);    return sb.toString();}​/* 輔助函式，將二叉樹存入 StringBuilder */void serialize(TreeNode root, StringBuilder sb) {    if (root == null) {        sb.append(NULL).append(SEP);        return;    }​    /****** 前序遍歷位置 ******/    sb.append(root.val).append(SEP);    /***********************/​    serialize(root.left, sb);    serialize(root.right, sb);}

現在，思考一下如何寫 deserialize 函式，將字串反過來構造二叉樹。

首先我們可以把字串轉化成列表：

String data = "1,2,#,4,#,#,3,#,#,";String[] nodes = data.split(",");

這樣，nodes 列表就是二叉樹的前序遍歷結果，問題轉化為：如何透過二叉樹的前序遍歷結果還原一棵二叉樹？

PS：一般語境下，單單前序遍歷結果是不能還原二叉樹結構的，因為缺少空指標的資訊，至少要得到前、中、後序遍歷中的兩種才能還原二叉樹。但是這裡的 node 列表包含空指標的資訊，所以只使用 node 列表就可以還原二叉樹。

根據我們剛才的分析，nodes 列表就是一棵打平的二叉樹：

那麼，反序列化過程也是一樣，先確定根節點 root，然後遵循前序遍歷的規則，遞迴生成左右子樹即可：

/* 主函式，將字串反序列化為二叉樹結構 */TreeNode deserialize(String data) {    // 將字串轉化成列表    LinkedList<String> nodes = new LinkedList<>();    for (String s : data.split(SEP)) {        nodes.addLast(s);    }    return deserialize(nodes);}​/* 輔助函式，透過 nodes 列表構造二叉樹 */TreeNode deserialize(LinkedList<String> nodes) {    if (nodes.isEmpty()) return null;​    /****** 前序遍歷位置 ******/    // 列表最左側就是根節點    String first = nodes.removeFirst();    if (first.equals(NULL)) return null;    TreeNode root = new TreeNode(Integer.parseInt(first));    /***********************/​    root.left = deserialize(nodes);    root.right = deserialize(nodes);​    return root;}

我們發現，根據樹的遞迴性質，nodes 列表的第一個元素就是一棵樹的根節點，所以只要將列表的第一個元素取出作為根節點，剩下的交給遞迴函式去解決即可。

三、後序遍歷解法

二叉樹的後續遍歷框架：

void traverse(TreeNode root) {    if (root == null) return;    traverse(root.left);    traverse(root.right);​    // 後序遍歷的程式碼}

明白了前序遍歷的解法，後序遍歷就比較容易理解了，我們首先實現 serialize 序列化方法，只需要稍微修改輔助方法即可：

/* 輔助函式，將二叉樹存入 StringBuilder */void serialize(TreeNode root, StringBuilder sb) {    if (root == null) {        sb.append(NULL).append(SEP);        return;    }        serialize(root.left, sb);    serialize(root.right, sb);    /****** 後序遍歷位置 ******/    sb.append(root.val).append(SEP);    /***********************/}

我們把對 StringBuilder 的拼接操作放到了後續遍歷的位置，後序遍歷導致結果的順序發生變化：

null,null,null,4,2,null,null,3,1,

關鍵的難點在於，如何實現後序遍歷的 deserialize 方法呢？是不是也簡單地將關鍵程式碼放到後序遍歷的位置就行了呢：

/* 輔助函式，透過 nodes 列表構造二叉樹 */TreeNode deserialize(LinkedList<String> nodes) {    if (nodes.isEmpty()) return null;    root.left = deserialize(nodes);    root.right = deserialize(nodes);    /****** 後序遍歷位置 ******/    String first = nodes.removeFirst();    if (first.equals(NULL)) return null;    TreeNode root = new TreeNode(Integer.parseInt(first));    /***********************/    return root;}

沒這麼簡單，顯然上述程式碼是錯誤的，變數都沒宣告呢，就開始用了？生搬硬套肯定是行不通的，回想剛才我們前序遍歷方法中的 deserialize 方法，第一件事情在做什麼？

deserialize 方法首先尋找 root 節點的值，然後遞迴計算左右子節點。那麼我們這裡也應該順著這個基本思路走，後續遍歷中，root 節點的值能不能找到？再看一眼剛才的圖：

可見，root 的值是列表的最後一個元素。我們應該從後往前取出列表元素，先用最後一個元素構造 root，然後遞迴呼叫生成 root 的左右子樹。注意，根據上圖，從後往前在 nodes 列表中取元素，一定要先構造 root.right 子樹，後構造 root.left 子樹。

看完整程式碼：

/* 主函式，將字串反序列化為二叉樹結構 */TreeNode deserialize(String data) {    LinkedList<String> nodes = new LinkedList<>();    for (String s : data.split(SEP)) {        nodes.addLast(s);    }    return deserialize(nodes);}/* 輔助函式，透過 nodes 列表構造二叉樹 */TreeNode deserialize(LinkedList<String> nodes) {    if (nodes.isEmpty()) return null;    // 從後往前取出元素    String last = nodes.removeLast();    if (last.equals(NULL)) return null;    TreeNode root = new TreeNode(Integer.parseInt(last));    // 限構造右子樹，後構造左子樹    root.right = deserialize(nodes);    root.left = deserialize(nodes);        return root;}

至此，後續遍歷實現的序列化、反序列化方法也都實現了。

四、中序遍歷解法

先說結論，中序遍歷的方式行不通，因為無法實現反序列化方法 deserialize。

序列化方法 serialize 依然容易，只要把字串的拼接操作放到中序遍歷的位置就行了：

/* 輔助函式，將二叉樹存入 StringBuilder */void serialize(TreeNode root, StringBuilder sb) {    if (root == null) {        sb.append(NULL).append(SEP);        return;    }    serialize(root.left, sb);    /****** 中序遍歷位置 ******/    sb.append(root.val).append(SEP);    /***********************/    serialize(root.right, sb);}

但是，我們剛才說了，要想實現反序列方法，首先要構造 root 節點。前序遍歷得到的 nodes 列表中，第一個元素是 root 節點的值；後序遍歷得到的 nodes 列表中，最後一個元素是 root 節點的值。

你看上面這段中序遍歷的程式碼，root 的值被夾在兩棵子樹的中間，也就是在 nodes 列表的中間，我們不知道確切的索引位置，所以無法找到 root 節點，也就無法進行反序列化。

五、層級遍歷解法

首先，先寫出層級遍歷二叉樹的程式碼框架：

void traverse(TreeNode root) {    if (root == null) return;    // 初始化佇列，將 root 加入佇列    Queue<TreeNode> q = new LinkedList<>();    q.offer(root);        while (!q.isEmpty()) {        TreeNode cur = q.poll();        /* 層級遍歷程式碼位置 */        System.out.println(root.val);        /*****************/        if (cur.left != null) {            q.offer(cur.left);        }                if (cur.right != null) {            q.offer(cur.right);        }    }}

上述程式碼是標準的二叉樹層級遍歷框架，從上到下，從左到右列印每一層二叉樹節點的值，可以看到，佇列 q 中不會存在 null 指標。

不過我們在反序列化的過程中是需要記錄空指標 null 的，所以可以把標準的層級遍歷框架略作修改：

void traverse(TreeNode root) {    if (root == null) return;    // 初始化佇列，將 root 加入佇列    Queue<TreeNode> q = new LinkedList<>();    q.offer(root);        while (!q.isEmpty()) {        TreeNode cur = q.poll();        /* 層級遍歷程式碼位置 */        if (cur == null) continue;        System.out.println(root.val);        /*****************/        q.offer(cur.left);        q.offer(cur.right);    }}

這樣也可以完成層級遍歷，只不過我們把對空指標的檢驗從「將元素加入佇列」的時候改成了「從佇列取出元素」的時候。

那麼我們完全仿照這個框架即可寫出序列化方法：

String SEP = ",";String NULL = "#";/* 將二叉樹序列化為字串 */String serialize(TreeNode root) {    if (root == null) return "";    StringBuilder sb = new StringBuilder();    // 初始化佇列，將 root 加入佇列    Queue<TreeNode> q = new LinkedList<>();    q.offer(root);        while (!q.isEmpty()) {        TreeNode cur = q.poll();                /* 層級遍歷程式碼位置 */        if (cur == null) {            sb.append(NULL).append(SEP);            continue;        }        sb.append(cur.val).append(SEP);        /*****************/        q.offer(cur.left);        q.offer(cur.right);    }        return sb.toString();}

層級遍歷序列化得出的結果如下圖：

可以看到，每一個非空節點都會對應兩個子節點，那麼反序列化的思路也是用佇列進行層級遍歷，同時用索引 i 記錄對應子節點的位置：

/* 將字串反序列化為二叉樹結構 */TreeNode deserialize(String data) {    if (data.isEmpty()) return null;    String[] nodes = data.split(SEP);    // 第一個元素就是 root 的值    TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));    // 佇列 q 記錄父節點，將 root 加入佇列    Queue<TreeNode> q = new LinkedList<>();    q.offer(root);    for (int i = 1; i < nodes.length; ) {        // 佇列中存的都是父節點        TreeNode parent = q.poll();        // 父節點對應的左側子節點的值        String left = nodes[i++];        if (!left.equals(NULL)) {            parent.left = new TreeNode(Integer.parseInt(left));            q.offer(parent.left);        } else {            parent.left = null;        }        // 父節點對應的右側子節點的值        String right = nodes[i++];        if (!right.equals(NULL)) {            parent.right = new TreeNode(Integer.parseInt(right));            q.offer(parent.right);        } else {            parent.right = null;        }    }    return root;}

這段程式碼可以考驗一下你的框架思維。仔細看一看 for 迴圈部分的程式碼，發現這不就是標準層級遍歷的程式碼衍生出來的嘛：

while (!q.isEmpty()) {    TreeNode cur = q.poll();    if (cur.left != null) {        q.offer(cur.left);    }        if (cur.right != null) {        q.offer(cur.right);    }}

只不過，標準的層級遍歷在操作二叉樹節點 TreeNode，而我們的函式在操作 nodes[i]，這也恰恰是反序列化的目的嘛。

到這裡，我們對於二叉樹的序列化和反序列化的幾種方法就全部講完了。