Notice
250x250
Recent Posts
Recent Comments
Link
넘치게 채우기
[LeetCode] 938. Range Sum of BST 본문
728x90
반응형
https://leetcode.com/problems/range-sum-of-bst/description/
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);
}
};
728x90
반응형
'PS > LeetCode' 카테고리의 다른 글
[LeetCode] 2385. Amount of Time for Binary Tree to Be Infected (0) | 2024.01.10 |
---|---|
[LeetCode] 872. Leaf-Similar Trees (0) | 2024.01.09 |
[LeetCode] 446. Arithmetic Slices II - Subsequence (0) | 2024.01.07 |
[LeetCode] 1235. Maximum Profit in Job Scheduling (0) | 2024.01.06 |
[LeetCode] 300. Longest Increasing Subsequence (0) | 2024.01.05 |