Search Range in Binary Search Tree

Every time when we're doing recursion to the next level, we check that if we should go to that side.
If our current value has already been smaller or equal to the  lower bound, we know that there's not any candidates in the left subtree. For the same reason, if our current value is larger than the upper bound, we know that there's no need for us to go to the right hand side.
If the search range is very small compare to the input size, our time complexity is approximately equal to logn. Generally our time complexity is between O(logn) and O(n).

也可以把result作为一个global variable，这样不用一直carry result list

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
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) {
        // write your code here
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (root == null) return result;
        searchRangeHelper(root, k1, k2, result);
        return result;
    }
    private void searchRangeHelper(TreeNode root, int lowerBound, int upperBound, ArrayList<Integer> result) {
        if (root == null) return;
        if (root.val > lowerBound) searchRangeHelper(root.left, lowerBound, upperBound, result);
     
        if (root.val >= lowerBound && root.val <= upperBound) result.add(root.val);
     
        if (root.val < upperBound) searchRangeHelper(root.right, lowerBound, upperBound, result);
    }
}