Get the list of keys in a given binary search tree in a given range[min, max] in ascending order, both min and max are inclusive.

Examples

    5

  /    \

3        8

/ \ \

1 4 11

get the keys in [2, 5] in ascending order, result is [3, 4, 5]

Corner Cases

• What if there are no keys in the given range? Return an empty list in this case.

Solution: inorder traversal + 条件。当root.key > min时，要traverse root.left；当root.key在[min, max]时，加入ans；当root.key < max时，要traverse root.right

  public List<Integer> getRange(TreeNode root, int min, int max) {
    List<Integer> ans = new ArrayList<Integer>();
    helper(ans, root, min, max);
    return ans;
  }
  private void helper(List<Integer> ans, TreeNode root, int min, int max) {
    if (root == null) {
      return;
    }
    if (root.key > min) {
      helper(ans, root.left, min, max);
    }
    if (min <= root.key && root.key <= max) {
      ans.add(root.key);
    }
    if (root.key < max) {
      helper(ans, root.right, min, max);
    }
  }