題目描述
請實作兩個函式，分別用來序列化和反序列化二叉樹
二叉樹的序列化是指：把一棵二叉樹按照某種遍歷方式的結果以某種格式保存為字串，從而使得記憶體中建立起來的二叉樹可以持久保存，序列化可以基于先序、中序、后序、層序的二叉樹遍歷方式來進行修改，序列化的結果是一個字串，序列化時通過 某種符號表示空節點（#），以 ！ 表示一個結點值的結束（value!），
二叉樹的反序列化是指：根據某種遍歷順序得到的序列化字串結果str，重構二叉樹，
思路
中序遍歷二叉樹的應用，時間復雜度O(lgn)，空間復雜度O(lgn)，
代碼
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
int index = -1;
String[] nodeList = null;
String Serialize(TreeNode root) {
if(root == null) {
return "#!";
} else {
return root.val + "!" + Serialize(root.left) + Serialize(root.right);
}
}
TreeNode Deserialize(String str) {
if(nodeList == null) {
nodeList = str.split("!");
}
index++;
TreeNode curr = null;
if(index < nodeList.length) {
if(!nodeList[index].equals("#")) {
curr = new TreeNode(Integer.parseInt(nodeList[index]));
curr.left = Deserialize(str);
curr.right = Deserialize(str);
}
}
return curr;
}
}
筆記
index記錄遞回程序中的下標，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/57191.html
標籤：其他
上一篇：動態規劃專題總結
下一篇：二叉搜索樹的第k個結點