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
先序遍历整棵树，然后数字就翻译成 val + "," 空指针就翻译成 "n,"
然后一系列处理过后，完成工作。
难点在于deserialize
类似于，给你一个 pre-order的访问顺序的数组，恢复出这个普通的,general binary tree.
依旧采用dfs
设置一个全局变量 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的头结点一定出现在该范围数组的最左侧。
最左侧的左子树，也一定出现在数组的最左侧。
所以curr不断往右移，当碰到null时，不再递归。
相当于从左侧开始，把整个binary tree慢慢做了出来。
意会下。
复杂度是O(n)
也正好差不多对应了一道题目，
给你一个pre-order array, 恢复出一个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 每次作为参数做递归。这样每次变化的值都可以存下来。
然后也可以通过 post-order 恢复。差不多的原理。
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;
}
然后这篇文章的衍生版讨论了，采用非递归来恢复。
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));
其实一共有两个数据结构。
首先是一个队列queue，用于存放 parent node
然后数列访问的正好是其 左右孩子结点。
所以每次都要判断 arr[i] and arr[i + 1]
因为加密的时候，对于非null的结点，就一定会保存其左右孩子结点的信息，哪怕他们使null。
所以解密的时候，采用队列的方式。每次从队列里面弹出来的结点，其左右孩子的信息正好存在当前 treeArr[i] and treeArr[i + 1] 里面。
然后还有一些优化的余地。
因为leaf node 都跟着两个null 的左右孩子，浪费了加密信息的空间。
可以分成 internal node and external node
参考网页：
http://www.geeksforgeeks.org/serialize-deserialize-binary-tree/
当树结点是 linked list 时，也可以通过这个层序遍历来实现。
只不过，加密的时候必须要注明其儿子结点的个数
node value / number of child nodes
然后，binary tree中是访问 i , i + 1
这里就是访问,
for (int j = i, j < i + n; j++) {...}
**
这道题目里面牵扯到了许多我以前没有关注过的地方。
给你一个pre-order or post-order array, 恢复出BST
或者给你一个含有value和null 的string array, 恢复出binary tree
然后递归的方法，非递归的方法。
对于这种dfs，我也是第一次碰到。
目前能够想到的dfs有三种。
第一种，类似于 combination, permutation 那类题目的
dfs() {
if (special case) {.... return....}
else {
for (int i = begin; i < end; i++) {
dfs(i, ...
);
}
}
**
复杂度是，O(2 ^ n)
第二种，类似于
- Generate Parentheses -
http://www.jianshu.com/p/2c9e588def78
的思想。
分成两种情况dfs
if (...) { dfs(...); }
else { dfs(...); }
复杂度暂时想不清楚。
第三种，就是这道题目里面的dfs
设置一个index
一步一步移动。
if (...) {...}
else {
dfs(...);
dfs(...);
}
这种将binary tree serialize的做法，在web programming里面，应该很常见的，虽然到目前为止我还没有碰到过。但这的确是对树的三种遍历加层序遍历的最好应用。
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 遍历一棵树，同时标识出空节点。
然后 decode 的时候，恢复出这个binary tree
那么，什么情况下可以恢复呢？
1 . pre-order / post-order + 标识出空节点
2 . pre-order / post-order + binary search tree
于是有个题：
给你一个 BST 的 preorder / postorder 序列，恢复出这个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
