leetcode习题分类汇总- Stack/Heap篇

Binary Tree Inorder Traversal-二叉树的中序遍历,迭代

思路:while循环,用栈迭代,左中右加到list里




### Binary Tree Preorder Traversal-二叉树的前序遍历



思路:一样的思路,中左右,只不过迭代的顺序不同,多加练习




### Binary Tree Postorder Traversal-二叉树的后序遍历

思路:把前序遍历颠倒着来,利用linkedlist的addFirst()




### Binary Search Tree Iterator-实现二叉搜索树的迭代

思路:维护一个栈,从根节点开始,每次迭代地将根节点的左孩子压入栈,直到左孩子为空为止。

调用next()方法时,弹出栈顶,如果被弹出的元素拥有右孩子,则以右孩子为根,将其左孩子迭代压栈。



### Valid Parentheses-Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.


思路:用栈的push,pop以及isEmpty()来判断是否符合条件



### Min Stack-设计一个栈的push(),pop(),top(),getMin()操作

思路:维护两个栈,还有一个维护最小值




### Merge k Sorted Lists-归并k个有序链表

思路:
(1)
这道题目在分布式系统中非常常见,来自不同client的sorted list要在central server上面merge起来。
这个题目一般有两种做法,下面一一介绍并且分析复杂度。 第一种做法比较容易想到,就是有点类似于MergeSort的思路,
就是分治法,不了解MergeSort的朋友,请参见归并排序-维基百科,是一个比较经典的O(nlogn)的排序算法,
还是比较重要的。思路是先分成两个子任务,然后递归求子任务,最后回溯回来。这个题目也是这样,先把k个list分成两半,然后继续划分,知道剩下两个list就合并起来我们来分析一下上述算法的时间复杂度。假设总共有k个list,每个list的最大长度是n,那么运行时间满足递推式T(k) = 2T(k/2)+O(nk)。根据主定理,可以算出算法的总复杂度是O(nklogk) 。如果不了解主定理的朋友,可以参见主定理-维基百科。空间复杂度的话是递归栈的大小O(logk)。

(2)接下来我们来看第二种方法。这种方法用到了堆的数据结构,思路比较难想到,但是其实原理比较简单。维护一个大小为k的堆,

 每次取堆顶的最小元素放到结果中,然后读取该元素的下一个元素放入堆中,重新维护好。因为每个链表是有序的,每次又是去当前k
个元素中最小的,所以当所有链表都读完时结束,这个时候所有元素按从小到大放在结果链表中。
这个算法每个元素要读取一次,即是kn次,然后每次读取元素要把新元素插入堆中要logk的复杂度,
所以总时间复杂度是O(nklogk)。空间复杂度是堆的大小,即为O(k)。
感觉就是链表的堆排序实现嘛。自己感觉还是挺少见的…

总结:一般是借助栈或者堆来进行遍历,重排序或者判断,这块自己复习的有点潦草了。