Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- geometry
- 코딩테스트
- array
- Number Theory
- greedy
- hash table
- Counting
- Matrix
- two pointers
- simulation
- 구현
- sorting
- 파이썬
- Class
- Stack
- Method
- Math
- Binary Tree
- bit manipulation
- dynamic programming
- implement
- string
- Binary Search
- 코테
- 자바
- Data Structure
- SQL
- database
- java
- Tree
Archives
- Today
- Total
코린이의 소소한 공부노트
[LeetCode/Easy] 938. Range Sum of BST 본문
1. Input
1) TreeNode root
2) int low
3) int high
2. Output
1) root에 있는 노드 값 중에서 [low, high] 범위 내의 값만 더한 결과를 반환
3. Constraint
1) 노드 수의 범위는 [1, 2*10^4]이다.
2) 1 <= Node.val <= 10^5
3) 1 <= low <= high <= 10^5
4) root내의 모든 노드 값에는 중복이 없다.
4. Example
Input: root = [10,5,15,3,7,null,18], low = 7, high = 15 -> Output: 32
설명: [7,15]내의 노드 값은 10, 15, 7이 있으므로 세 수의 합인 32를 반환한다.
5. Code
1) 첫 코드(2023/06/06)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int rangeSumBST(TreeNode root, int low, int high) {
int sum = 0;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
TreeNode c;
while(!q.isEmpty()){
c = q.remove();
if(low<=c.val && c.val<=high){
sum += c.val;
if(c.left!=null)
q.add(c.left);
if(c.right!=null)
q.add(c.right);
} else if(c.val<low && c.right!=null)
q.add(c.right);
else if(high<c.val && c.left!=null)
q.add(c.left);
}
return sum;
}
}
- 16%, 78%
- 다른 사람들 풀이를 확인해보니 재귀함수를 이용한 쪽이 더 빨랐다.
'코딩테스트 풀이 > JAVA' 카테고리의 다른 글
[LeetCode/Easy] 999. Available Captures for Rook (0) | 2023.06.06 |
---|---|
[LeetCode/Easy] 965. Univalued Binary Tree (0) | 2023.06.06 |
[LeetCode/Easy] 914. X of a Kind in a Deck of Cards (0) | 2023.06.05 |
[LeetCode/Easy] 897. Increasing Order Search Tree (0) | 2023.06.05 |
[백준 온라인 저지] 11727. 2×n 타일링 2 (0) | 2023.06.01 |