国庆在忙着学习框架的东西，所以没怎么看相关的算法和数据结构的东西，现在有时间所以又做了点题目上传，警醒一下自己。
第三周，算法给生活加点料。
1.二叉树的序列化与反序列化
首先呢明确说明是序列化说明是反序列化：
二叉树->文件，称之为序列化；文件->二叉树，称之为反序列化
想法：针对序列化呢，我们要明确如何区别数字，比如一课二叉树的数组表示为：1，2，33 如果序列化后没有其他操作，就会变成1233，那么我们就没有办法对其进行还原操作。我们呢选择在每一个数后面添加一个“！”表示区别。当我们的数据存完后会有一个null值，我们呢就加一个“#”表示这个节点为空。
首先实现的是先序遍历的代码：
public class Demo10 {
public class Node{
public int value;
public Node left;
public Node right;
}
public String searchByPre(Node head){
if(head == null)
return "#!";
//首先就是每一个值后面加一个 ！
String res = head.value + "!";
//由于是先序遍历，所以根节点之后就是遍历做孩子之后再右孩子。实现的方法为递归查询遍历
res += searchByPre(head.left);
res += searchByPre(head.right);
return res;
}
}接着呢我们再把上面代码生成的文件返回成一棵树的模样。也就是当我们遍历的时候如果遇到了！就证明之前这个数为一个值，然后去掉！后再紧接着遍历，如果碰到#就证明这个数的一个子节点为null，然后再转向另一个子节点继续刚才操作即可。
import java.util.LinkedList;
import java.util.Queue;
public class Demo10_2 {
public class Node{
public int value;
public Node left;
public Node right;
//作用就是方便转换时候调用
public Node(Integer valueOf) {
}
public Node() {
}
}
public Node reconByPreString(String preStr){
//实现根据！的分离切片操作
String[] values = preStr.split("!");
//创建一个队列用于暂时保存数据
Queue<String> queue = new LinkedList<>();
for (int i = 0; i != values.length; i++) {
queue.offer(values[i]);
}
return reconPreOrder(queue);
}
public Node reconPreOrder(Queue<String> queue){
//获取首位元素并删除
String value = queue.poll();
if(value.equals("#")){
return null;
}
//递归的还原整棵树
Node head = new Node(Integer.valueOf(value));
head.left = reconPreOrder(queue);
head.right = reconPreOrder(queue);
return head;
}
}注：其实序列化和反序列化都可以使用先中后序的遍历方法或者是层次遍历，我们这里只取了先序。
2.判断t1树是否包含t2树的全部拓扑结构
说白了就是判断t2树是否是t1的子树嘛。
想法：首先确定t2的根节点值是否在t1中存在，如果存在就开始对照遍历。并且当t2遍历完全后（t1刚好结束或者仍有余且没有因为不相同的数据中断）就返回true。否则返回false。如果中断，就在开始遍历的节点下继续遍历t1寻找之前动作。时间复杂度大致为O(N*M)
public class Demo11 {
public class Node{
public int value;
public Node left;
public Node right;
//生成代参和无参构造函数
public Node(int data){
this.value = data;
}
public Node(){
}
}
public boolean contains(Node t1,Node t2){
//当t1为空肯定不包含，或者t2为空肯定包含
if(t2 == null)
return true;
if(t1 == null)
return false;
//判断当前节点以及其左右孩子是否相同，不同就去遍历左孩子，再不行就遍历右孩子
return check(t1,t2) || contains(t1.left,t2) || contains(t1.right,t2);
}
public boolean check(Node h,Node t2){
if(t2 == null)
return true;
if(h == null || h.value != t2.value)
return false;
//判断当前节点的左右孩子是否相同
return check(h.left,t2.right) && check(h.right,t2.right);
}
}注：由于嵌套关系太紧密，所以会大量的消耗资源，但是相对于的这个代码容易理解且好写。
3.根据后续数组重建搜索二叉树
首页呢要了解什么是搜索二叉树，说白了就是二叉排序树。就是树的左子树小于右子树的树的总称。
给定的是一个没有重复值的数组。
想法：因为是后续遍历的，所以根节点一定最后一个遍历到，那么它肯定在数组的最后。同理可以得到小于它的树肯定在前一半，而大于它的肯定在后一半。那么就递归的来吧。
public class Demo12 {
public boolean isPostArray(int[] arr){
if(arr == null || arr.length == 0)
return false;
return isPost(arr,0,arr.length-1);
}
public boolean isPost(int[] arr, int start,int end){
//长度为零时，返回
if(start == end)
return true;
//分别记录位置以及最后对比的元素
int less = -1;
int more = end;
for (int i = start; i < end; i++) {
//先找到左边的值
if(arr[end] > arr[i]){
less = i;
}else{
more = more == end?i:more;
}
}
//如果界限刚好在最后一位
if(less == -1 || more == end){
return isPost(arr, start ,end - 1);
}
//如果界限值不匹配
if(less != more -1){
return false;
}
//左右子树依次递归
return isPost(arr,start,less) && isPost(arr,more,end -1);
}
}进一步加强一下:能否把这个数组还原成二叉树?
public class Demo12_2 {
public class Node{
public int value;
public Node left;
public Node right;
public Node(int value){
this.value = value;
}
public Node posArrayToBST(int[] posArr){
if(posArr == null)
return null;
return posToBST(posArr,0,posArr.length-1);
}
public Node posToBST(int[] posArr,int start,int end){
if(start > end)
return null;
//先找到根节点，然后依次寻找左右节点
Node head = new Node(posArr[end]);
//记录位置
int less = -1;
int more = end;
for (int i = start ; i < end; i++) {
//先找到界限
if(posArr[end] > posArr[i]){
less = i;
}else{
//more给定界限后一个值
more = more == end ? i : more;
}
}
//递归的构建树
head.left = posToBST(posArr,start,less);
head.right = posToBST(posArr,more,end-1);
return head;
}
}
}4.判断一棵树是否时完全二叉树
很简单嘛，只要层次遍历，除了叶子节点外其他节点都有左右孩子即为完全二叉树。一说到层次遍历肯定会用到queue结构嘛。
import java.util.LinkedList;
import java.util.Queue;
public class Demo13 {
public class Node{
public int value;
public Node left;
public Node right;
public Node(int value){
this.value = value;
}
}
public boolean isBST(Node head){
if(head == null)
return true;
//队列用于保存节点的值
Queue<Node> queue = new LinkedList<>();
//定义一个叶子节点以及左右节点
boolean leaf = false;
Node lt = null;
Node rt = null;
//先放入根节点
queue.offer(head);
while (!queue.isEmpty()){
head = queue.poll();
lt = head.left;
rt = head.right;
if((leaf && (lt != null || rt != null)) || (lt == null && rt != null)){
return false;
}
//左边不为空就放入
if(lt != null)
queue.offer(lt);
//右边不为空也放入
if(rt != null) {
queue.offer(rt);
}else{
//如果右边为空就时叶子节点
leaf = true;
}
}
return true;
}
}
