- Published on
Leetcode - 938. Range Sum of BST
- Authors
- Name
- Indo Yoon
Table of Contents
문제
[Loading...
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
LeetCode
](https://leetcode.com/problems/range-sum-of-bst/)
풀이
쉽게 풀 수 있지만 BST의 특징을 활용하면 pruning이 가능하다.
class Solution:
cur_sum = 0
def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
def get_sum(node):
if not node:
return 0
get_sum(node.left)
get_sum(node.right)
if low <= node.val <= high:
self.cur_sum += node.val
get_sum(root)
return self.cur_sum
DFS with pruning
class Solution:
cur_sum = 0
def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
def get_sum(node):
if node:
if node.val > high:
get_sum(node.left)
elif node.val < low:
get_sum(node.right)
else:
get_sum(node.left)
get_sum(node.right)
if low <= node.val <= high:
self.cur_sum += node.val
get_sum(root)
return self.cur_sum
DFS with pruning 2
class Solution:
cur_sum = 0
def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
stack = [root]
cur_sum = 0
while stack:
node = stack.pop()
if not node:
continue
if node.val > low:
stack.append(node.left)
if node.val < high:
stack.append(node.right)
if low <= node.val <= high:
cur_sum += node.val
return cur_sum
BFS with pruning
class Solution:
cur_sum = 0
def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
queue = [root]
cur_sum = 0
while queue:
node = queue.pop()
if not node:
continue
if node.val > low:
queue.append(node.left)
if node.val < high:
queue.append(node.right)
if low <= node.val <= high:
cur_sum += node.val
return cur_sum