Search Range in Binary Search Tree
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.
Example
For example, if k1 = 10 and k2 = 22, then your function should print 12, 20 and 22.
20
/ \
8 22
/ \
4 12
class Solution {
public:
/**
* @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.
*/
vector<int> searchRange(TreeNode* root, int k1, int k2) {
// write your code here
vector<int> result;
if (root == NULL) {
return result;
}
stack<TreeNode*> stack;
while (root && root->val > k2) {
root = root->left;
}
if (root) {
stack.push(root);
} else {
return result;
}
while(true) {
if (stack.empty()) return result;
TreeNode* cur = stack.top();
//push all the potential left children
while (cur) {
//bug here
if (cur->val >= k1 && cur->left && cur->left->val <= k2) {
stack.push(cur->left);
}
cur = cur->left;
}
// pop until the one which has a right child
cur = stack.top();
while (cur->right == NULL) {
stack.pop();
if (cur->val >= k1 && cur->val <= k2) {
result.push_back(cur->val);
}
if (stack.empty()) return result;
cur = stack.top();
}
if (cur->val >= k1 && cur->val <= k2) {
result.push_back(cur->val);
}
stack.pop();
//push the right node into the stack, bug here
//if (cur->val >= k1 && cur->val <= k2) {
stack.push(cur->right);
//}
}
}
};
No comments:
Post a Comment