Search Range in Binary Search Tree

Java

public class Solution {
    /**
     * @param root: param root: The root of the binary search tree
     * @param k1: An integer
     * @param k2: An integer
     * @return: return: Return all keys that k1<=key<=k2 in ascending order
     */
		private ArrayList<Integer> results;
		
		public List<Integer> searchRange(TreeNode root, int k1, int k2) {
			results = new ArrayList<Integer>();
			helper(root, k1, k2);
			return results;
		}
		
		private void helper(TreeNode root, int k1, int k2) {
			if (root == null) return;
			if (root.val > k1) helper(root.left, k1, k2);
		if (k1 <= root.val && root.val <= k2) results.add(root.val);
			if (root.val < k2) helper(root.right, k1, k2);
			
		}
}



Time Complexity: O(N)   介于 logN 和 O(N)之间
Space Complexity