Search Range in Binary Search Tr

Search Range in Binary Search Tree.png

解題思路 ：

recursive 作業順序：

1. 往左檢查 left child 只要有符合 > k1 的 node 就繼續往左找更小的可能符合要求的點
2. 檢查當前的點 如果數值 x 符合 k1 <= x <= k2 就放入 result
3. 向右檢查 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;
}

};