Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Find all the keys of tree in range k1 to k2. i.e. print all x such that k1<=x<=k2 and x is a key of given BST. Return all the keys in ascending order.
If k1 = 10 and k2 = 22, then your function should return [12, 20, 22].
20
/ 8 22
/ 4 12
SOLUTION :
这个的核心就是DFS，再说就是递归，所以这个题先定义一个递归函数，然后不停的递归判断就可以了，但是这个题要比普通DFS要有一些优化，因为很明显的是，（以root为指针dfs）当root.val < k1 OR root.val > k2 也就是说这个指针已经出了给定的条件了，这时候就没必要再往这个方向DFS了，再往下走结果也不会满足条件了。然后就是这题为了方便DFS加入一个全局变量，所以具体的看代码：
public class Solution {
/**
* @param root: The root of the binary search tree.
* @param k1 and k2: range k1 to k2.
* @return: Return all keys that k1<=key<=k2 in ascending order.
*/
private ArrayList<Integer> result;//定义一个全局变量
public ArrayList<Integer> searchRange(TreeNode root, int k1, int k2) {
result = new ArrayList<Integer>();
helper(root, k1, k2);
return result;
}
private void helper(TreeNode root, int k1, int k2){
if (root == null){
return;
}
if (k1 < root.val){
helper(root.left, k1, k2);
}
if (k1 <= root.val && root.val <= k2){
result.add(root.val);
}
if (k2 > root.val){
helper(root.right, k1, k2);
}
}
}
[Lintcode] Search Range in Binary Search Tree
原文：http://www.cnblogs.com/tritritri/p/4859902.html