Serialize and Deserialize Binary Tree

首先，很抱歉，停更了幾天。因?yàn)樯×?，燒到?9度，喉嚨疼的要命，不知道是不是跟北京最近的霧霾天氣有關(guān)?，F(xiàn)在好一些了，從今天起恢復(fù)更新。

今天是一道有關(guān)二叉樹的題目，來自LeetCode，難度為Medium，Acceptance為24.6%。

題目如下

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

    1
   / \
  2   3
      / \
     4   5

as [1,2,3,null,null,4,5], just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Note:
Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

解題思路及代碼見閱讀原文

回復(fù)0000查看更多題目

解題思路

首先，老規(guī)矩，看到二叉樹，想到二叉樹的三種遍歷方式。

然后，這里需要序列化和反序列化二叉樹，可以采用的方法很多了。多種遍歷方式都可以，只有在序列化和反序列化時(shí)采用相同的遍歷方式即可。其中較為簡單的是前序遍歷和層次遍歷。

因?yàn)椴捎?strong>層次遍歷行需要利用隊(duì)列，會(huì)多引入一種數(shù)據(jù)結(jié)構(gòu)，所以這里采用前序遍歷，這種方法也比較容易理解和實(shí)現(xiàn)。

• 序列化，即將二叉樹轉(zhuǎn)成字符串。因?yàn)槎鏄渲邪?code>null節(jié)點(diǎn)。需要采用一個(gè)特殊字符標(biāo)記，因?yàn)檫@里的二叉樹的值都是數(shù)字，所以可以采用非數(shù)字作為標(biāo)記，如采用X。每個(gè)節(jié)點(diǎn)間用,分割。然后就是按照前序遍歷的方法，輸入二叉樹成字符串，較為簡單，不再贅述。

• 反序列化，即將剛才生成的字符串轉(zhuǎn)換成二叉樹。首先，將字符串按照,split成字符串數(shù)組的形式，該數(shù)組中每一個(gè)元素即為一個(gè)二叉樹的節(jié)點(diǎn)。
  這里本來可以很簡單的用一個(gè)全局變量記錄，當(dāng)前遍歷的數(shù)組index，但是因?yàn)轭}目中要求采用stateless的方式，所以必須換種方式。
  可以采用List的方式，將已經(jīng)遍歷的節(jié)點(diǎn)刪除，剩下的就是當(dāng)該字符串不是X時(shí)，按照前序遍歷的方式重建二叉樹。

代碼如下

Java版

public class Codec {
    private static final String spliter = ",";
    private static final String NN = "X";

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        buildString(root, sb);
        return sb.toString();
    }

    private void buildString(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append(NN).append(spliter);
        } else {
            sb.append(node.val).append(spliter);
            buildString(node.left, sb);
            buildString(node.right,sb);
        }
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        Deque<String> nodes = new LinkedList<>();
        nodes.addAll(Arrays.asList(data.split(spliter)));
        return buildTree(nodes);
    }

    private TreeNode buildTree(Deque<String> nodes) {
        String val = nodes.remove();
        if (val.equals(NN)) return null;
        else {
            TreeNode node = new TreeNode(Integer.valueOf(val));
            node.left = buildTree(nodes);
            node.right = buildTree(nodes);
            return node;
        }
    }
}

關(guān)注我
該公眾號會(huì)每天推送常見面試題，包括解題思路是代碼，希望對找工作的同學(xué)有所幫助

image