My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
public String serialize(TreeNode root) {
if (root == null)
return null;
StringBuilder ret = new StringBuilder();
dfs(ret, root);
String retStr = ret.toString();
return retStr.substring(0, retStr.length() - 1);
}
private void dfs(StringBuilder ret, TreeNode root) {
if (root == null) {
ret.append("n;");
return;
}
int val = root.val;
ret.append(val + ";");
dfs(ret, root.left);
dfs(ret, root.right);
}
// Decodes your encoded data to tree.
private int curr = 0;
public TreeNode deserialize(String data) {
if (data == null || data.length() == 0)
return null;
String[] treeArr = data.split(";");
return ddfs(treeArr);
}
private TreeNode ddfs(String[] treeArr) {
if (curr < 0 || curr >= treeArr.length)
return null;
String word = treeArr[curr];
curr++;
if (word.equals("n")) { // null node
return null;
}
else {
int val = Integer.parseInt(word);
TreeNode root = new TreeNode(val);
root.left = ddfs(treeArr);
root.right = ddfs(treeArr);
return root;
}
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
這個類型的題目以前從來沒有碰到過。
可以分成兩塊： serialize 和 deserialize
類似于encode 和 decode
加密的方式有哪些缭保？
遞歸或者非遞歸汛闸。
pre-order, post-order
OR
level-order
第一個解法采用的是 pre-order
先序遍歷整棵樹，然后數(shù)字就翻譯成 val + "," 空指針就翻譯成 "n,"
然后一系列處理過后艺骂，完成工作诸老。
難點在于deserialize
類似于，給你一個 pre-order的訪問順序的數(shù)組钳恕，恢復(fù)出這個普通的,general binary tree.
依舊采用dfs
設(shè)置一個全局變量 curr = 0
然后别伏，每次進入dfs中時蹄衷，
curr++;
if (treeArr[curr].equals("n")) {...}
else {
TreeNode root = new TreeNode(val);
root.left = dfs(...);
root.right = dfs(...);
return root;
}
因為 pre-order時，每個sub tree的頭結(jié)點一定出現(xiàn)在該范圍數(shù)組的最左側(cè)厘肮。
最左側(cè)的左子樹愧口，也一定出現(xiàn)在數(shù)組的最左側(cè)。
所以curr不斷往右移类茂，當(dāng)碰到null時耍属，不再遞歸。
相當(dāng)于從左側(cè)開始巩检，把整個binary tree慢慢做了出來厚骗。
意會下。
復(fù)雜度是O(n)
也正好差不多對應(yīng)了一道題目兢哭，
給你一個pre-order array, 恢復(fù)出一個BST
http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/
也是用的相同的思想领舰。
對于這道題木，
My code:
private int begin = 0;
public TreeNode formBST(int[] nums) {
if (nums == null || nums.length == 0)
return null;
return dfs(nums, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private TreeNode dfs(int[] nums, int min, int max) {
if (begin >= nums.length)
return null;
int val = nums[begin];
if (val > min && val < max) {
begin++;
TreeNode root = new TreeNode(val);
root.left = dfs(nums, min, val);
root.right = dfs(nums, val, max);
return root;
}
return null;
}
全局變量begin可以用一個 private class Index 來代替迟螺，將Index 每次作為參數(shù)做遞歸冲秽。這樣每次變化的值都可以存下來。
然后也可以通過 post-order 恢復(fù)煮仇。差不多的原理劳跃。
My code:
private int end = 0;
public TreeNode formBST(int[] nums) {
if (nums == null || nums.length == 0)
return null;
end = nums.length - 1;
return ddfs(nums, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private TreeNode ddfs(int[] nums, int min, int max) {
if (end < 0)
return null;
if (nums[end] > min && nums[end] < max) {
TreeNode root = new TreeNode(nums[end]);
end--;
root.right = ddfs(nums, root.val, max);
root.left = ddfs(nums, min, root.val);
return root;
}
else
return null;
}
然后這篇文章的衍生版討論了，采用非遞歸來恢復(fù)浙垫。
http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversal-set-2/
有時間再看下吧刨仑。
然后再說下，serialize and deserialize 的第二種方法夹姥，
非遞歸杉武，采用隊列 + 層序遍歷的方法。
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null)
return null;
Queue<TreeNode> q = new LinkedList<TreeNode>();
StringBuilder ret = new StringBuilder();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode temp = q.poll();
if (temp == null) {
ret.append("n,");
continue;
}
ret.append(temp.val + ",");
q.offer(temp.left);
q.offer(temp.right);
}
}
String retStr = ret.toString();
return retStr.substring(0, retStr.length() - 1);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null || data.length() == 0)
return null;
String[] treeArr = data.split(",");
Queue<TreeNode> q = new LinkedList<TreeNode>();
TreeNode root = new TreeNode(Integer.parseInt(treeArr[0]));
q.offer(root);
int i = 1;
while (i < treeArr.length) {
TreeNode temp = q.poll();
if (!treeArr[i].equals("n")) {
int val = Integer.parseInt(treeArr[i]);
temp.left = new TreeNode(val);
q.offer(temp.left);
}
i++;
if (!treeArr[i].equals("n")) {
int val = Integer.parseInt(treeArr[i]);
temp.right = new TreeNode(val);
q.offer(temp.right);
}
i++;
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
其實一共有兩個數(shù)據(jù)結(jié)構(gòu)辙售。
首先是一個隊列queue轻抱，用于存放 parent node
然后數(shù)列訪問的正好是其 左右孩子結(jié)點。
所以每次都要判斷 arr[i] and arr[i + 1]
因為加密的時候旦部，對于非null的結(jié)點祈搜，就一定會保存其左右孩子結(jié)點的信息，哪怕他們使null士八。
所以解密的時候容燕，采用隊列的方式。每次從隊列里面彈出來的結(jié)點婚度，其左右孩子的信息正好存在當(dāng)前 treeArr[i] and treeArr[i + 1] 里面蘸秘。
然后還有一些優(yōu)化的余地。
因為leaf node 都跟著兩個null 的左右孩子，浪費了加密信息的空間醋虏。
可以分成 internal node and external node
參考網(wǎng)頁：
http://www.geeksforgeeks.org/serialize-deserialize-binary-tree/
當(dāng)樹結(jié)點是 linked list 時寻咒，也可以通過這個層序遍歷來實現(xiàn)。
只不過颈嚼，加密的時候必須要注明其兒子結(jié)點的個數(shù)
node value / number of child nodes
然后毛秘，binary tree中是訪問 i , i + 1
這里就是訪問,
for (int j = i, j < i + n; j++) {...}
**
這道題目里面牽扯到了許多我以前沒有關(guān)注過的地方。
給你一個pre-order or post-order array, 恢復(fù)出BST
或者給你一個含有value和null 的string array, 恢復(fù)出binary tree
然后遞歸的方法粘舟，非遞歸的方法熔脂。
對于這種dfs，我也是第一次碰到柑肴。
目前能夠想到的dfs有三種霞揉。
第一種，類似于 combination, permutation 那類題目的
dfs() {
if (special case) {.... return....}
else {
for (int i = begin; i < end; i++) {
dfs(i, ...
);
}
}
**
復(fù)雜度是晰骑，O(2 ^ n)
第二種适秩，類似于
- Generate Parentheses -
http://www.reibang.com/p/2c9e588def78
的思想。
分成兩種情況dfs
if (...) { dfs(...); }
else { dfs(...); }
復(fù)雜度暫時想不清楚硕舆。
第三種秽荞，就是這道題目里面的dfs
設(shè)置一個index
一步一步移動。
if (...) {...}
else {
dfs(...);
dfs(...);
}
這種將binary tree serialize的做法抚官，在web programming里面扬跋，應(yīng)該很常見的，雖然到目前為止我還沒有碰到過凌节。但這的確是對樹的三種遍歷加層序遍歷的最好應(yīng)用钦听。
Anyway, Good luck, Richardo!
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
dfs(root, sb);
return sb.toString();
}
private void dfs(TreeNode root, StringBuilder sb) {
if (root == null) {
sb.append("X,");
}
else {
sb.append(root.val).append(",");
dfs(root.left, sb);
dfs(root.right, sb);
}
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] parts = data.split(",");
Queue<String> q = new LinkedList<String>();
for (int i = 0; i < parts.length; i++) {
if (parts[i].length() != 0) {
q.offer(parts[i]);
}
}
return ddfs(q);
}
private TreeNode ddfs(Queue<String> q) {
String s = q.poll();
if (s.equals("X")) {
return null;
}
else {
TreeNode root = new TreeNode(Integer.parseInt(s));
root.left = ddfs(q);
root.right = ddfs(q);
return root;
}
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
reference:
https://discuss.leetcode.com/topic/28029/easy-to-understand-java-solution/2
思路主要就是， pre-order 遍歷一棵樹倍奢，同時標(biāo)識出空節(jié)點朴上。
然后 decode 的時候，恢復(fù)出這個binary tree
那么卒煞，什么情況下可以恢復(fù)呢痪宰？
1 . pre-order / post-order + 標(biāo)識出空節(jié)點
2 . pre-order / post-order + binary search tree
于是有個題：
給你一個 BST 的 preorder / postorder 序列，恢復(fù)出這個BST
pre-order
private int counter_Pre = 0;
public TreeNode restoreBST_Pre(int[] nums) {
return helper_Pre(nums, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private TreeNode helper_Pre(int[] nums, int min, int max) {
if (counter_Pre >= nums.length) {
return null;
}
int val = nums[counter_Pre];
if (val > min && val < max) {
counter_Pre++;
TreeNode root = new TreeNode(val);
root.left = helper_Pre(nums, min, val);
root.right = helper_Pre(nums, val, max);
return root;
}
return null;
}
post-order
int counter_Post;
public TreeNode restoreBST_Post(int[] nums) {
counter_Post = nums.length - 1;
return helper_Post(nums, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private TreeNode helper_Post(int[] nums, int min, int max) {
if (counter_Post < 0) {
return null;
}
int val = nums[counter_Post];
if (min < val && val < max) {
counter_Post--;
TreeNode root = new TreeNode(val);
root.right = helper_Post(nums, val, max);
root.left = helper_Post(nums, min, val);
return root;
}
return null;
}
Anyway, Good luck, Richardo! -- 09/23/2016
