Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.9 kB
1
Indexable
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    
    void sumBST(TreeNode* curr_node, int low, int high, int& sum)
    {
        if (curr_node != nullptr)
        {
            if (curr_node->val <= high && curr_node->val >= low)
                sum += curr_node->val;
            
            if (curr_node->val >= low)
                sumBST(curr_node->left, low, high, sum);
            
            if (curr_node->val <= high)
                sumBST(curr_node->right, low, high, sum);
        }
    }
    
    int rangeSumBST(TreeNode* root, int low, int high) {
        TreeNode* curr_node = root;
        int sum = 0;
        
        while (curr_node->val < low)
            curr_node = curr_node->right;
        while (curr_node->val > high)
            curr_node = curr_node->left;
        
// METHOD 01: Using stack
//         stack<TreeNode*> node_list;
//         node_list.push(curr_node);
//         while (node_list.size() != 0)
//         {
//             curr_node = node_list.top();
//             node_list.pop();
            
//             if (curr_node->val <= high && curr_node->val >= low)
//                 sum += curr_node->val;
            
//             if (curr_node->left != nullptr)
//                 node_list.push(curr_node->left);
            
//             if (curr_node->right != nullptr)
//                 node_list.push(curr_node->right);
//         }
 
// METHOD 02: Using recursion
        sumBST(curr_node, low, high, sum);
        
        return sum;
    }
};