描述
設(shè)計(jì)一個(gè)算法圈澈，并編寫(xiě)代碼來(lái)序列化和反序列化二叉樹(shù)痘昌。將樹(shù)寫(xiě)入一個(gè)文件被稱(chēng)為“序列化”茂嗓，讀取文件后重建同樣的二叉樹(shù)被稱(chēng)為“反序列化”餐茵。
如何反序列化或序列化二叉樹(shù)是沒(méi)有限制的，你只需要確笔鑫可以將二叉樹(shù)序列化為一個(gè)字符串忿族，并且可以將字符串反序列化為原來(lái)的樹(shù)結(jié)構(gòu)。
對(duì)二進(jìn)制樹(shù)進(jìn)行反序列化或序列化的方式?jīng)]有限制蝌矛，LintCode將您的serialize輸出作為deserialize的輸入道批，它不會(huì)檢查序列化的結(jié)果。
樣例
給出一個(gè)測(cè)試數(shù)據(jù)樣例朴读， 二叉樹(shù){3,9,20,#,#,15,7}屹徘，表示如下的樹(shù)結(jié)構(gòu)：
? 3
/ \
9? 20
? /? \
15? 7
我們的數(shù)據(jù)是進(jìn)行 BFS 遍歷得到的。當(dāng)你測(cè)試結(jié)果 wrong answer時(shí)衅金，你可以作為輸入調(diào)試你的代碼。
你可以采用其他的方法進(jìn)行序列化和反序列化簿煌。
代碼
GitHub 的源代碼氮唯，請(qǐng)?jiān)L問(wèn)下面的鏈接：
package com.ossez.lang.tutorial.tests.lintcode;
import java.util.ArrayList;
import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import com.ossez.lang.tutorial.models.TreeNode;
/**
* <p>
* 7
* <ul>
* <li>@see <a href=
* "https://www.cwiki.us/display/ITCLASSIFICATION/Serialize+and+Deserialize+Binary+Tree">https://www.cwiki.us/display/ITCLASSIFICATION/Serialize+and+Deserialize+Binary+Tree</a>
* <li>@see<a href=
* "https://www.lintcode.com/problem/serialize-and-deserialize-binary-tree">https://www.lintcode.com/problem/serialize-and-deserialize-binary-tree</a>
* </ul>
* </p>
*
* @author YuCheng
*
*/
public class LintCode0007SerializeAndDeserialize {
? private final static Logger logger = LoggerFactory.getLogger(LintCode0007SerializeAndDeserialize.class);
? /**
? *
? */
? @Test
? public void testMain() {
? ? logger.debug("BEGIN");
? ? String data = "{3,9,20,#,#,15,7}";
? ? System.out.println(serialize(deserialize(data)));
? }
? /**
? * Deserialize from array to tree
? *
? * @param data
? * @return
? */
? private TreeNode deserialize(String data) {
? ? // NULL CHECK
? ? if (data.equals("{}")) {
? ? ? return null;
? ? }
? ? ArrayList<TreeNode> treeList = new ArrayList<TreeNode>();
? ? data = data.replace("{", "");
? ? data = data.replace("}", "");
? ? String[] vals = data.split(",");
? ? // INSERT ROOT
? ? TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
? ? treeList.add(root);
? ? int index = 0;
? ? boolean isLeftChild = true;
? ? for (int i = 1; i < vals.length; i++) {
? ? ? if (!vals[i].equals("#")) {
? ? ? ? TreeNode node = new TreeNode(Integer.parseInt(vals[i]));
? ? ? ? if (isLeftChild) {
? ? ? ? ? treeList.get(index).left = node;
? ? ? ? } else {
? ? ? ? ? treeList.get(index).right = node;
? ? ? ? }
? ? ? ? treeList.add(node);
? ? ? }
? ? ? // LEVEL
? ? ? if (!isLeftChild) {
? ? ? ? index++;
? ? ? }
? ? ? // MOVE TO RIGHT OR NEXT LEVEL
? ? ? isLeftChild = !isLeftChild;
? ? }
? ? return root;
? }
? /**
? *
? * @param root
? * @return
? */
? public String serialize(TreeNode root) {
? ? // write your code here
? ? if (root == null) {
? ? ? return "{}";
? ? }
? ? ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
? ? queue.add(root);
? ? for (int i = 0; i < queue.size(); i++) {
? ? ? TreeNode node = queue.get(i);
? ? ? if (node == null) {
? ? ? ? continue;
? ? ? }
? ? ? queue.add(node.left);
? ? ? queue.add(node.right);
? ? }
? ? while (queue.get(queue.size() - 1) == null) {
? ? ? queue.remove(queue.size() - 1);
? ? }
? ? StringBuilder sb = new StringBuilder();
? ? sb.append("{");
? ? sb.append(queue.get(0).val);
? ? for (int i = 1; i < queue.size(); i++) {
? ? ? if (queue.get(i) == null) {
? ? ? ? sb.append(",#");
? ? ? } else {
? ? ? ? sb.append(",");
? ? ? ? sb.append(queue.get(i).val);
? ? ? }
? ? }
? ? sb.append("}");
? ? return sb.toString();
? }
}
點(diǎn)評(píng)
本題目主要需要你對(duì)二叉樹(shù)的遍歷方法有所了解。
遍歷二叉樹(shù)主要有 2 類(lèi)方法姨伟，分別為深度優(yōu)先（DFS）和廣度優(yōu)先（BFS）惩琉。
在深度優(yōu)先中，你有又可以使用前序夺荒，中序和后序搜索方法瞒渠，你可以使用遞歸或者非遞歸算法實(shí)現(xiàn)。對(duì)于廣度優(yōu)先算法技扼，一般都會(huì)采用非遞歸的實(shí)現(xiàn)方法進(jìn)行實(shí)現(xiàn)伍玖。
