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
- leetcode풀이
- leetcode 풀기
- 릿코드
- 상가수익률계산기
- 알고리즘풀이
- 릿코드풀기
- 릿코드풀이
- 코틀린기초
- 파이썬 릿코드
- 파이썬알고리즘
- python 알고리즘
- python zip_longest
- 파이썬 알고리즘 풀기
- python sorted
- 잇츠디모
- 파이썬 프로그래머스
- python priority queue
- 파이썬 알고리즘
- python 릿코드
- 릿코드 풀기
- python xor
- leetcode풀기
- 파이썬릿코드
- 파이썬알고리즘풀기
- 알고리즘풀기
- 파이썬릿코드풀기
- 릿코드 파이썬
- binary search
- python Leetcode
- LeetCode
Archives
- Today
- Total
소프트웨어에 대한 모든 것
LeetCode 풀기 - 938. Range Sum of BST 본문
반응형
938. Range Sum of BST
https://leetcode.com/problems/range-sum-of-bst/
문제)
솔루션1) - inorder traversal
이진 트리의 전위, 중위, 후위 순회 뭐든 사용해도 상관없습니다.
트리의 전체를 순회하면서 val이 low, high의 사이 값인 경우 저장해서 sum을 구합니다.
class Solution:
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
res = []
def traversal(node):
if node is None:
return
if low <= node.val <= high:
res.append(node.val)
if low < node.val:
traversal(node.left)
if node.val < high:
traversal(node.right)
traversal(root)
return sum(res)
솔루션2) - stack 사용
stack 자료구조를 사용합니다.
이진 트리 구조를 이용해서 탐색 범위를 줄여가기 때문에 솔루션1) 보다 더 빠르게 range sum을 구할 수 있습니다.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
stack = [root]
range_sum = 0
while stack:
node = stack.pop()
if node:
if low < node.val:
stack.append(node.left)
if node.val < high:
stack.append(node.right)
if low <= node.val <= high:
range_sum += node.val
return range_sum
반응형
'알고리즘 > LeetCode' 카테고리의 다른 글
LeetCode 풀기 - 897. Increasing Order Search Tree (0) | 2021.11.26 |
---|---|
LeetCode 풀기 - 1315. Sum of Nodes with Even-Valued Grandparent (0) | 2021.11.24 |
LeetCode 풀기 - 450. Delete Node in a BST (0) | 2021.11.24 |
LeetCode 풀기 - 1351. Count Negative Numbers in a Sorted Matrix (0) | 2021.11.24 |
LeetCode 풀기 - 1002. Find Common Characters (0) | 2021.11.23 |
Comments