[LintCode]Search Range In Binary Search Tree

首先是brute-force的方法， inorder看是不是在range里，在的话就加入。时间复杂度是O(N)。显然面试官不可能希望这个方法。

既然考虑到我们是在binary search tree里搜索在range里的数，显然会有更有效的方法。首先假设我们找到了最高的节点top在给出的范围[lo, hi]中。那么所有在top左子树中的节点不可能大于top.value，更不可能大于hi。右子树的节点同理。假设现在我们在左子树的一个节点上curr, 如果curr.val大于等于lo，那么curr和 curr的右子树都应该被加入结果集。左子树需要继续探索。相反如果curr.val小于lo，那么curr和curr的左子树都不能可能是我们要的结果，但是我们还应该探索curr的右子树，因为右子树可能会有满足要求的结果。在top的右子树中情况是一样的。最后注意加入结果集的时候按照inorder的顺序。时间复杂度是O(log N + k), k为最后结果集的大小。

上述过程可以用下列图片表示：

代码如下：

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

view raw BST range query.java hosted with ❤ by GitHub