Given two values `k1`

and `k2`

(where `k1 < k2`

) and a root pointer to a binary search tree, find all the keys in the tree in range `k1`

to `k2`

. Return all the keys in ascending order.

Example

Give `k1 = 10`

, `k2 = 22`

and the following tree, return `[12, 20, 22]`

.

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.
*/
public ArrayList < Integer > searchRange ( TreeNode root , int k1 , int k2 ) {
ArrayList < Integer > res = new ArrayList <>();
search ( root , k1 , k2 , res );
return res ;
}
private void search ( TreeNode root , int k1 , int k2 , ArrayList < Integer > res ) {
if ( root == null )
return ;
if ( root . val < k1 ) {
search ( root . right , k1 , k2 , res );
}
else if ( root . val > k2 ) {
search ( root . left , k1 , k2 , res );
}
else {
search ( root . left , k1 , k2 , res );
res . add ( root . val );
search ( root . right , k1 , k2 , res );
}
}
}

public class TreeNode {
public int val ;
public TreeNode left , right ;
public TreeNode ( int val ) {
this . val = val ;
this . left = this . right = null ;
}
}