[LeetCode] 938. Range Sum of BST

 

https://leetcode.com/problems/range-sum-of-bst/description/

Range Sum of BST - LeetCode

leetcode - Range Sum of BST

문제 유형 : bfs/dfs, 트리

문제 난이도 : Easy

 

문제

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].

 

이진 탐색 트리의 루트 노드가 주어진다. 그리고 low와 high가 주어진다.

트리의 노드 중에서 닫힌 구간 [low, high]안에 들어오는 값들을 모두 더한 값을 구하시오.

 

풀이

나는 전위순회를 이용하여 합을 구했다.

우선, 현재의 노드가 NULL이면 0을 반환한다.

만약 현재 노드가 범위 안에 들어온다면, 값을 더한다. 범위 밖이라면 더하지 않는다.

왼쪽 서브트리의 총합 + 오른쪽 서브트리의 총합 + 현재 값을 리턴한다. (범위 밖이면 현재 값=0으로 설정)

 

코드

C++

/**
 * 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) {}
 * };
 */

static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

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