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],存入结果。
代码: