51.节点之和最大的路径
思路:这里考察的是后序遍历,对后序遍历每一个节点来说,当前点可以视作为终点,向上透传的时候要注意分几类情况,左右孩子最多只能选一个,或者自己也不选。
52.展平二叉搜索树
思路:中序遍历的应用,方法一:可以将中序遍历加入到slice中遍历处理,方法二,直接在遍历的过程中进行修改。
53.二叉搜索树中的中序后继
思路:两种做法,一种是根据中序遍历,记录pre的指向,第二种是根据大小关系直接进行遍历即可。
54.所有大于等于节点的值之和
思路:这是一个变形的后续遍历,只需要借助一个全局的临时变量即可。
55.二叉搜索树迭代器
思路:前序遍历的应用。
56.二叉搜索树中两个节点之和
思路:dfs+二分
57.值和下标之差都在给定的范围内
思路:普通遍历或者可以考虑滑动窗口。
58.日程表
思路:判断两个数段相交,(s1 < e2 && s2 < e1)
59.数据流的第 K 大数值
思路:go实现优先队列
type KthLargest struct {
sort.IntSlice
k int
}
func Constructor(k int, nums []int) KthLargest {
kl := KthLargest{k: k}
for _, val := range nums {
kl.Add(val)
}
return kl
}
func (kl *KthLargest) Push(v interface{}) {
kl.IntSlice = append(kl.IntSlice, v.(int))
}
func (kl *KthLargest) Pop() interface{} {
a := kl.IntSlice
v := a[len(a)-1]
kl.IntSlice = a[:len(a)-1]
return v
}
func (kl *KthLargest) Add(val int) int {
heap.Push(kl, val)
if kl.Len() > kl.k {
heap.Pop(kl)
}
return kl.IntSlice[0]
}
60.出现频率最高的 k 个数字
思路:可以考虑一般普通解法,先用map,在用slice.sort,方法二:考虑用优先队列(heap实现的是大小根堆,通过对根堆进行出栈,就能获得升序或者降序的序列)
func topKFrequent(nums []int, k int) []int {
occurrences := map[int]int{}
for _, num := range nums {
occurrences[num]++
}
h := &IHeap{}
heap.Init(h)
for key, value := range occurrences {
heap.Push(h, [2]int{key, value})
if h.Len() > k {
heap.Pop(h)
}
}
ret := make([]int, k)
for i := 0; i < k; i++ {
ret[k - i - 1] = heap.Pop(h).([2]int)[0]
}
return ret
}
type IHeap [][2]int
func (h IHeap) Len() int { return len(h) }
func (h IHeap) Less(i, j int) bool { return h[i][1] < h[j][1] }
func (h IHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IHeap) Push(x interface{}) {
*h = append(*h, x.([2]int))
}
func (h *IHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}