Description
Given a binary search tree and a range [k1, k2], return node values within a given range in ascending order.
Example
Example 1:
Input：{5},6,10
Output：[]
5
it will be serialized {5}
No number between 6 and 10
Example 2:
Input：{20,8,22,4,12},10,22
Output：[12,20,22]
Explanation：
20
/ \
8 22
/ \
4 12
it will be serialized {20,8,22,4,12}
[12,20,22] between 10 and 22
思路：
1.用了和901类似的想法，用stack将树看作数组遍历到相应区间，这个时间复杂度应该是O(h)？
2.直接遍历一遍二叉树，满足条件的结果就append到结果中去，对结果进行排序，这个时间复杂度应该是O(n + （k2-k1)log(k2-k1))?
3.用DFS，从给定的BST的根节点开始查找，如果当前节点大于k1，就向左子树搜索，如果当前节点小于k2，就继续向右子树搜索。如果位于[k1,k2]，存入结果。
代码：
网友评论