LeetCode 220. Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

思路

基本思路是,假设当前运行到nums[i]的位置,则需要往前看k个数,并且找到其中任意一个数x满足 nums[i]-t <= x <=nums[i]+t。可以利用一个大小为k的二叉搜索树解决搜索范围的问题(问题就转变为:找到第一个>=nums[i]-t的数,判断他是否<=nums[i]+t)。整个算法的时间复杂度是O(N * logk),N为数组长度。
下面代码中用set实现,set是用红黑树实现的。

代码


 

LeetCode 173. Binary Search Tree Iterator

思路

画一个简单的BST,然后可以看出有三种情况

  • 如果当前节点有右孩子,那就在右子树里找到值最小的那个,显然是右子树里最左下侧的那个节点
  • 如果当前节点没有右孩子,由于左子树的值肯定都比当前节点的值小,左右要找父节点
    • 如果找到某个父节点的值比当前节点值大,那这个父节点就是下一节点
    • 否则,当前节点就是最后一个节点

因此,需要一个栈结构记录当前节点的父亲们(有点像调用栈)。

测试例:NULL根节点,只有一个节点,只有单侧树

代码

 

LeetCode 102. Binary Tree Level Order Traversal

练手水题,直接贴代码。快转正面试了,虚啊,鬼晓得BOSS会问点什么。