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 { void pushLeft(stack<TreeNode *> &st, TreeNode *root, int k1) { while(root) { st.push(root); if (root->val < k1) break; root = root->left; } } 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) { stack<TreeNode *> st; vector<int> output; pushLeft(st, root, k1); while(st.size() > 0) { TreeNode *t = st.top(); st.pop(); if (t->val >= k1 && t->val <= k2) output.push_back(t->val); if (t->val <= k2) pushLeft(st, t->right, k1); } return output; } };
No comments:
Post a Comment