data-structure-and-algorithm/leetcode/binary_search_tree/search_range_in_BST.cpp at master · chachaxw/data-structure-and-algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**
 * @Author: Chacha
 * @Date: 2018-12-19 22:21:32
 * @Last Modified by: Chacha
 * @Last Modified time: 2022-03-02 10:49:31
 */

/***********************************************************************************
 * Given a binary search tree and a range [k1, k2], return all elements in the given range.
 *
 * Example:
 *  If k1 = 10 and k2 = 22, then your function should return [12, 20, 22].
 *     20
 *    /  \
 *   8   22
 *  / \
 * 4  12
 *
 * Source: https://www.lintcode.com/problem/search-range-in-binary-search-tree/description
 ************************************************************************************/

#include <iostream>
#include <vector>

using namespace std;

/**
 * Definition for a binary tree node.
 */
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void inorder_defs(vector<int> &ret, TreeNode *root, int k1, int k2)
{

    if (root == NULL)
    {
        return;
    }

    inorder_defs(ret, root->left, k1, k2);

    if ((root->val >= k1) && (root->val <= k2))
    {
        ret.push_back(root->val);
    }

    inorder_defs(ret, root->left, k1, k2);
}

vector<int> searchRange(TreeNode *root, int k1, int k2)
{
    vector<int> result;
    inorder_defs(result, root, k1, k2);

    return result;
}

int main()
{
    return 0;
}