第62題：二叉搜索樹的第k個(gè)節(jié)點(diǎn)
難易度：??
題目描述:
給定一棵二叉搜索樹，請(qǐng)找出其中的第k小的結(jié)點(diǎn)。
例如， （5，3急侥，7砌滞，2侮邀，4，6贝润，8） 中绊茧，按結(jié)點(diǎn)數(shù)值大小順序第三小結(jié)點(diǎn)的值為4。
解析：
二叉搜索樹的特點(diǎn)就是如果中序遍歷二叉搜索樹打掘，打印出來的節(jié)點(diǎn)value值會(huì)按照從小到大的順序進(jìn)行排列华畏，可以利用這一點(diǎn)，用一個(gè)變量去標(biāo)記index值尊蚁，當(dāng)index等于k時(shí)亡笑，返回該節(jié)點(diǎn)即可。
代碼如下:
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.Stack;
public class Solution {
TreeNode KthNode(TreeNode pRoot, int k){
if(pRoot == null || k < 0){
return null;
}
int index = 0;
Stack<TreeNode> stack = new Stack<>();
while(pRoot != null || !stack.isEmpty()){
if(pRoot != null){
stack.push(pRoot);
pRoot = pRoot.left;
}else{
pRoot = stack.pop();
index++;
// do sth
if(index == k){
return pRoot;
}
pRoot = pRoot.right;
}
}
return null;
}
}
第63題：數(shù)據(jù)流中的中位數(shù)
難易度：???
如何得到一個(gè)數(shù)據(jù)流中的中位數(shù)横朋？
如果從數(shù)據(jù)流中讀出奇數(shù)個(gè)數(shù)值仑乌，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值。
如果從數(shù)據(jù)流中讀出偶數(shù)個(gè)數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后中間兩個(gè)數(shù)的平均值晰甚。
我們使用Insert()方法讀取數(shù)據(jù)流衙传，使用GetMedian()方法獲取當(dāng)前讀取數(shù)據(jù)的中位數(shù)。
如果你用一個(gè)數(shù)組去接收流吐出的數(shù)字厕九，那么收集流吐出的數(shù)字很簡(jiǎn)單蓖捶，但是如果要獲取中位數(shù)的話就要對(duì)數(shù)組進(jìn)行一次排序，如果要求流每次吐出一個(gè)數(shù)字就獲取一次中位數(shù)扁远，那么就要頻繁地對(duì)數(shù)組進(jìn)行排序操作俊鱼。解決的方法就是使用堆結(jié)構(gòu)來解決這個(gè)問題：設(shè)計(jì)一個(gè)最大堆，和一個(gè)最小堆穿香，每次流吐出數(shù)字的時(shí)候都和最大堆的堆頂作比較亭引，如果小于等于最大堆堆頂就放入最大堆，如果大于最大堆的堆頂則放入最小堆皮获。同時(shí)我們還需要保證最大堆的數(shù)據(jù)量不能比最小堆中的數(shù)據(jù)量大超過1焙蚓，反之亦是如此,也就是要保持最大堆數(shù)據(jù)量N和最小堆的數(shù)據(jù)量M的關(guān)系為 |N-M| <= 1,如何保持這種關(guān)系呢？一旦破壞了這種關(guān)系的平衡洒宝，我們就讓最大堆的頂部或者最小堆的頂部彈出购公，讓這個(gè)最大的數(shù)字進(jìn)入到最小堆里面，或者是讓最小堆的最小的數(shù)字加到最大堆里面雁歌，如圖示意：
假設(shè)這個(gè)數(shù)據(jù)流吐出的數(shù)字依次是 5->6->4->7->3->8->1
左側(cè)為最大堆數(shù)字?jǐn)?shù)量為N宏浩，右側(cè)為最小堆數(shù)字?jǐn)?shù)量為M,沒有破壞過 |N-M| <= 1的規(guī)定，如果這個(gè)時(shí)候數(shù)據(jù)流吐出的數(shù)字為0靠瞎，那么就要add到最大堆里面比庄，這個(gè)時(shí)候N-M = 2破壞了兩堆數(shù)量上的平衡，所以要把最大堆的堆頂彈入到最小堆中去乏盐，操作如下：
首先將數(shù)字0 add 到最大堆中
交換最大堆首尾數(shù)字
將最大堆末尾數(shù)字(5) add 到最小堆
接下來就是heapify操作了佳窑，對(duì)最大堆中的堆頂0進(jìn)行heapify,首先要判斷它的兩個(gè)孩子誰更大，誰大跟誰交換父能，直到滿足最大堆的結(jié)構(gòu)為止
本題的思路就是使用一個(gè)最大堆和一個(gè)最小堆解決神凑，優(yōu)先級(jí)隊(duì)列PriorityQueue即可以滿足本題的求解，代碼如下:
import java.util.Comparator;
import java.util.PriorityQueue;
public class Solution {
private PriorityQueue<Integer> minHeap = new PriorityQueue<>(new MinHeapCompare());
private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new MaxHeapCompare());
public static class MinHeapCompare implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
}
public static class MaxHeapCompare implements Comparator<Integer>{
@Override
public int compare(Integer o1,Integer o2){
return o2 - o1;
}
}
private void modify(){
if(maxHeap.size() == minHeap.size() + 2){
minHeap.add(maxHeap.poll());
}
if(minHeap.size() == maxHeap.size() + 2){
maxHeap.add(minHeap.poll());
}
}
public void Insert(Integer num) {
if(maxHeap.isEmpty()){
maxHeap.add(num);
return;
}
if(num <= maxHeap.peek()){
maxHeap.add(num);
}else{
if(minHeap.isEmpty()){
minHeap.add(num);
return;
}
if(num < minHeap.peek()){
maxHeap.add(num);
}else{
minHeap.add(num);
}
}
modify();
}
public Double GetMedian() {
if(maxHeap.isEmpty() && minHeap.isEmpty()){
return null;
}
int maxHeapSize = maxHeap.size();
int minHeapSize = minHeap.size();
int maxHeapHead = maxHeapSize == 0 ? 0 : maxHeap.peek();
int minHeapHead = minHeapSize == 0 ? 0 :minHeap.peek();
if(maxHeapSize == minHeapSize){
return ((double)(maxHeapHead + minHeapHead))/2;
}
return maxHeapSize > minHeapSize ? (double)maxHeapHead : (double)minHeapHead;
}
}
