Search Range in Binary Search Tree.png
解題思路 ：
recursive 作業順序：
- 往左檢查 left child 只要有符合 > k1 的 node 就繼續往左找更小的可能符合要求的點
- 檢查當前的點 如果數值 x 符合 k1 <= x <= k2 就放入 result
- 向右檢查 right child 只要符合 < k2 的 node 就繼續往右找更大的可能符合要求的點
C++ code :
<pre><code>
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.
*/
void findRange(TreeNode *root, int k1, int k2, vector<int> &res){
if(root->left && root->val > k1) findRange(root->left, k1, k2, res);
if(root->val >= k1 && root->val <= k2) res.emplace_back(root->val);
if(root->right && root->val < k2) findRange(root->right, k1, k2, res);
}
vector<int> searchRange(TreeNode* root, int k1, int k2) {
// write your code here
vector<int> res;
if(root != nullptr) findRange(root, k1, k2, res);
return res;
}
};
