Closest Binary Search Tree Value II.cpp

思路就是对predecessor和successor分别建立iterator，然后根据情况决定这一次是选predecessor的next还是successor的next，直到我们取到k个值位置。建立Binary Tree Iterator的思路可以参考这一题。这一题是类似的，我们以successor为例，区别就是我们不会把小于target的数push进stack，因为我们发现当前节点curr的值小于target的话，那么整个左子树我们就不需要考察了，直接去右子树继续构建stack。如果当前节点curr的值大于等于target，那么我们存入stack，方便之后遍历其右子树。显而易见，简历stack的时间复杂度为O(log n)，有了stack之后，我们就可以按照iterator的方法每次取一个值了。注意handle 和target值相等的node的时候，只需要predecessor和successor iterator其中一个handle就可以了。时间复杂度等于建stack + using iterator to find k elements = O(log n + k)，代码如下：