二叉树重构条件：
各个节点的value值保证唯一（这个很重要，不唯一无法重构），同时已知先序遍历结果和中序遍历结果或者是已知后序遍历结果和中序遍历结果。
二叉数重构代码：
public TreeNode getTree(String[] In,String[] Pos){
//In和Pos长度相同
if(In.length == 0){
return null;
}
int rootValue = Integer.parseInt(Pos[Pos.length - 1]);
TreeNode root = new TreeNode(rootValue);
if(In.length == 1){
return root;
}
int delimiterIndex;
for(delimiterIndex = 0; delimiterIndex < In.length; delimiterIndex++){
if(Integer.parseInt(In[delimiterIndex]) == rootValue){
break;
}
}
String[] leftIn = Arrays.copyOfRange(In,0,delimiterIndex);
String[] rightIn = Arrays.copyOfRange(In,delimiterIndex+1,In.length);
String[] leftPos = Arrays.copyOfRange(Pos,0,leftIn.length);
String[] rightPos = Arrays.copyOfRange(Pos,leftIn.length,Pos.length - 1);
root.left = getTree(leftIn,leftPos);
root.right = getTree(rightIn,rightPos);
return root;
}
二叉树的序列化和反序列化中：
注意点：value值可以重复出现，这时不能用重构的方法来反序列化。树结构可能不一致。
二叉树序列化代码和反序列化代码：
StringBuilder tmp;
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root == null){
return null;
}
tmp = new StringBuilder();
getMid(root);
return tmp.toString();
}
public void getMid(TreeNode root){
if(root == null){
tmp.append("null").append(",");
return ;
};
tmp.append(root.val).append(",");
getMid(root.left);
getMid(root.right);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data == null || data.length() == 0) return null;
String[] In = data.split(",");
LinkedList strings = new LinkedList(Arrays.asList(In));
return getTree(strings);
}
public TreeNode getTree(LinkedList In){
if(In.get(0).equals("null")){
In.remove(0);
return null;
}
TreeNode node = new TreeNode(Integer.parseInt(In.get(0)));
In.remove(0);
node.left = getTree(In);
node.right = getTree(In);
return node;
}
