Search Range in Binary Search Tree | Data Structure and Algorithm
Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Find all the keys of tree in range k1 to k2. i.e. print all x such that k1<=x<=k2 and x is a key of given BST. Return all the keys in ascending order.
A little inefficient: Use ArrayList<Integer> res as method argument.
可以优化的地方为「剪枝过程」的处理——不递归遍历不可能有解的节点
Use class variable.
private ArrayList<Integer> results;
http://blog.welkinlan.com/2015/05/22/search-range-in-binary-search-tree-lintcode-java/
Use InorderIterator to encapsulate traversal logic. But better add pruning logic into the iterator.
Read full article from Search Range in Binary Search Tree | Data Structure and Algorithm
Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Find all the keys of tree in range k1 to k2. i.e. print all x such that k1<=x<=k2 and x is a key of given BST. Return all the keys in ascending order.
For example, if k1 = 10 and k2 = 22, then your function should print 12, 20 and 22.
20
/ \
8 22
/ \
4 12 void inorder_dfs(vector<int> &ret, TreeNode *root, int k1, int k2) {
if (NULL == root) {
return;
}
inorder_dfs(ret, root->left, k1, k2);
if ((root->val >= k1) && (root->val <= k2)) {
ret.push_back(root->val);
}
inorder_dfs(ret, root->right, k1, k2);
}A little inefficient: Use ArrayList<Integer> res as method argument.
7 public ArrayList<Integer> searchRange(TreeNode root, int k1, int k2) { 8 ArrayList<Integer> res = searchRangeRecur(root,k1,k2); 9 return res; 10 } 12 public ArrayList<Integer> searchRangeRecur(TreeNode cur, int k1, int k2){ 13 ArrayList<Integer> res = new ArrayList<Integer>(); 14 if (cur==null) return res; 15 if (k1>k2) return res; 16 17 ArrayList<Integer> left = searchRangeRecur(cur.left,k1,Math.min(cur.val-1,k2)); 18 ArrayList<Integer> right = searchRangeRecur(cur.right,Math.max(cur.val+1,k1),k2); 19 20 res.addAll(left); 21 if (cur.val>=k1 && cur.val<=k2) res.add(cur.val); 22 res.addAll(right); 23 24 return res; 25 }http://blog.welkinlan.com/2015/05/22/search-range-in-binary-search-tree-lintcode-java/
可以优化的地方为「剪枝过程」的处理——不递归遍历不可能有解的节点
Use class variable.
private ArrayList<Integer> results;
public ArrayList<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);
} // else prune left tree
if (root.val >= k1 && root.val <= k2) {
results.add(root.val);
}
if (root.val < k2) {
helper(root.right, k1, k2);
} // else prune right tree
}
Iterative in-order traversal:http://blog.welkinlan.com/2015/05/22/search-range-in-binary-search-tree-lintcode-java/
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;
}
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
while (root != null || !stack.isEmpty()) {
//left
if (root != null) {
stack.push(root); // it should also add prune logic here, if root.val < k1, continue, no root=root.left.
root = root.left;
} else {
//root
root = stack.pop();
if (root.val >= k1 && root.val <= k2) {
result.add(root.val);
} else if (root.val > k2) { //pruning, optimization
break;
}
//right
root = root.right;
}
}
return result;
}
http://blog.csdn.net/martin_liang/article/details/45771979Use InorderIterator to encapsulate traversal logic. But better add pruning logic into the iterator.
BSTIterator(TreeNode *root) {
TreeNode *pCurNode = root;
while (pCurNode)
{
mStack.push(pCurNode);
pCurNode = pCurNode->left;
}
}
bool hasNext() {
if (mStack.size() > 0)
return true;
return false;
}
int next() {
TreeNode* retNode = mStack.top();
mStack.pop();
TreeNode *pCurNode = retNode;
if (pCurNode->right)
{
pCurNode = pCurNode->right;
while (pCurNode)
{
mStack.push(pCurNode);
pCurNode = pCurNode->left;
}
}
return retNode->val;
}
};
vector<int> searchRange(TreeNode* root, int k1, int k2) {
BSTIterator itr(root);
vector<int> retVector;
while (itr.hasNext())
{
int curVal = itr.next();
if (curVal >= k1 && curVal <= k2)
{
retVector.push_back(curVal);
}
}
return retVector;
}
Read full article from Search Range in Binary Search Tree | Data Structure and Algorithm
