[LintCode]Search Range In Binary Search Tree

首先是brute-force的方法， inorder看是不是在range里，在的话就加入。时间复杂度是O(N)。显然面试官不可能希望这个方法。

既然考虑到我们是在binary search tree里搜索在range里的数，显然会有更有效的方法。首先假设我们找到了最高的节点top在给出的范围[lo, hi]中。那么所有在top左子树中的节点不可能大于top.value，更不可能大于hi。右子树的节点同理。假设现在我们在左子树的一个节点上curr, 如果curr.val大于等于lo，那么curr和 curr的右子树都应该被加入结果集。左子树需要继续探索。相反如果curr.val小于lo，那么curr和curr的左子树都不能可能是我们要的结果，但是我们还应该探索curr的右子树，因为右子树可能会有满足要求的结果。在top的右子树中情况是一样的。最后注意加入结果集的时候按照inorder的顺序。时间复杂度是O(log N + k), k为最后结果集的大小。

上述过程可以用下列图片表示：

代码如下：