[LeetCode] 938. Range Sum of BST c++

• 문제

Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

 

이진탐색트리의 node중에 low와 high사이에 있는 값을 모두 더한 값을 구하는 문제이다.

• 문제 해결

class Solution {
public:
    int nSum = 0;
    int rangeSumBST(TreeNode* root, int low, int high) {
        
        if(root == NULL)
            return  nSum;
        
        if(root->val >= low && root-> val <= high){
            nSum += root->val;
        }
        
        rangeSumBST(root->left, low, high);
        rangeSumBST(root->right, low, high);
        
        return nSum;
    }
};

 

다른 방법

    int rangeSumBST(TreeNode* root, int L, int R) {
        int rangeSum(0);
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()){
            TreeNode* node = st.top(); st.pop();
            if(node->val>=L && node->val<=R) rangeSum+=node->val;
            if(node->val > L) {if(node->left) st.push(node->left);}
            if(node->val < R) {if(node->right) st.push(node->right);}
        }
        return rangeSum;
    }