《剑指offer》– 序列化二叉树、二叉搜索树的第k个节点、数据流中的中位数、滑动窗口的最大值

一、序列化二叉树：

1、题目：

请实现两个函数，分别用来序列化和反序列化二叉树。

2、解题思路：

（1）根据前序遍历规则完成序列化与反序列化。所谓序列化指的是遍历二叉树为字符串；所谓反序列化指的是依据字符串重新构造成二叉树。

（2）依据前序遍历序列来序列化二叉树，因为前序遍历序列是从根结点开始的。当在遍历二叉树时碰到Null指针时，这些Null指针被序列化为一个特殊的字符“#”。另外，结点之间的数值用逗号隔开。

3、代码实现：

public class Test20 {
	//序列化
	String Serialize(TreeNode root) {
		StringBuffer sb = new StringBuffer();
		if(root == null){
			sb.append("#,");
			return sb.toString();
		}
		sb.append(root.val+",");
		sb.append(Serialize(root.left));
		sb.append(Serialize(root.right));
		
        return sb.toString();
	}
	
	public int index = -1;
	int len =0;
	//反序列化
	TreeNode Deserialize(String str) {
		String[] strArray = str.split(",");
		len = str.length();
		return Deserialize2(strArray,str);
		
	}
	TreeNode Deserialize2(String[] strArray,String str){
		index++;

		TreeNode node = null;
		if(!strArray[index].equals("#")){
			node = new TreeNode(Integer.valueOf(strArray[index]));
			node.left = Deserialize2(strArray,str);
			node.right = Deserialize2(strArray,str);
		}
       return node;
	}
}


class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}

二、二叉搜索树的第k个节点：

1、题目：

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8）    中，按结点数值大小顺序第三小结点的值为4。

2、解题思路：

使用中序遍历找到第k个节点。

3、代码实现：

public class Test21 {
	/*
	如果没有if(node != null)这句话  那么那个root就是返回给上一级的父结点的，而不是递归结束的条件了,有了这句话过后，
	一旦返回了root，那么node就不会为空了，就一直一层层的递归出去到结束了。举第一个例子{8,6,5,7},1 答案应该是5，
	如果不加的时候，开始，root=8，node=kth（6,1），继续root=6，node=kth（5,1）root =5 返回null，
	这时向下执行index=k=1了，返回 5给root=6递归的时候的node，这时回到root=8了，往后面调右孩子的时候为空而把5给覆盖了。
	现在就为空了，有了这句话后虽然为空，但不把null返回，而是继续返回5，
	 */
	int index = 0;
	TreeNode KthNode(TreeNode pRoot, int k){
		if(pRoot != null){//中序遍历寻找第k个
			TreeNode node = KthNode(pRoot.left,k);
			if(node != null){
				return node;
			}
			
			index++;
			if(index == k){
				return pRoot;
			}
			
			node = KthNode(pRoot.right,k);
			if(node != null){
				return node;
			}
		}
		 return null;
	}
}


class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}

三、数据流中的中位数：

1、题目：

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

2、解题思路：

使用一个大顶堆和一个小顶堆，维持大顶堆的数都小于等于小顶堆的数，且两者的个数相等或差1。平均数就在两个堆顶的数之中。

3、代码实现：

public class Test23 {
	private int count = 0;
	//默认最小堆
	private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
	private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(11,new Comparator<Integer>() {
	    @Override
	    public int compare(Integer o1, Integer o2) {
	        return o2 - o1;
	    }
	});
	
	public void Insert(Integer num) {
		if(count %2 == 0){
			//当数据总数为偶数是，新加入的元素，应当进入小根堆，
			//（主意不是直接进入小跟堆，而是经过大根堆筛选后去大根堆中最大元素进入小根堆）
			//1、新加入的元素先入到大根堆，由大根堆筛选出堆中最大的元素
			maxHeap.offer(num);
			int filteredMaxNum = maxHeap.poll();
			//2.筛选后的 大根堆中的最大元素 进入小跟堆
			minHeap.offer(filteredMaxNum);
		}else{
			//当数据总数为奇数时，新加入的元素，应当进入大根堆
	        //（注意不是直接进入大根堆，而是经小根堆筛选后取小根堆中最大元素进入大根堆）
	        //1.新加入的元素先入到小根堆，由小根堆筛选出堆中最小的元素
			minHeap.offer(num);
			int filteredMinNum = minHeap.poll();
			//2.筛选后的【小根堆中的最小元素】进入大根堆
	        maxHeap.offer(filteredMinNum);
		}
		count++;
    }

    public Double GetMedian() {
    	if(count % 2 == 0 ){
    		return new Double((minHeap.peek()+maxHeap.peek()))/2;
    	}else{
    		return new Double(minHeap.peek());
    	}
    }
}

四、滑动窗口的最大值：

1、题目：

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

2、解题思路：

用一个双端队列，队列第一个位置保存当前窗口的最大值，当窗口滑动一次，进行下面的两个判断：
（1）判断当前最大值是否过期；
（2）新增加的值从队尾开始比较，把所有比他小的值丢掉。

3、代码实现：

public class Test22 {
	public ArrayList<Integer> maxInWindows(int [] num, int size){
		
		ArrayList<Integer> result = new ArrayList<Integer>();
		if(size == 0){
			return result;
		}
		
		int begin;
		//建立一个双端队列，注意：队列中存放的是下标
		ArrayDeque<Integer> queue = new ArrayDeque<Integer>();
		
		for(int i =0;i<num.length;i++){
			begin = i-size+1;//滑动窗口的起始位置。
			if(queue.isEmpty()){
				queue.add(i);
			}else if(begin>queue.peekFirst()){
				queue.pollFirst();
			}
			
			while( !queue.isEmpty() && num[queue.peekLast()]<=num[i]){
				queue.pollLast();
			}
			queue.add(i);
			
			if(begin>=0){
				result.add(num[queue.peekFirst()]);
			}
		}
		return result;
    }
}