[99클럽 코테 스터디 11일차 TIL] 938. Range Sum of BST

Problem

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

 

Sol

트리에서 low <= x <= high에 해당하는 x의 값을 찾아 더해주면 되는 문제

---

✔ BST(Binary Search Tree)

정렬된 이진트리로, 트리의 모든 노드 "x"에 대해 아래의 속성이 모두 참이어야 합니다.

• x 노드의 왼쪽 자식과 모든 하위 항목은 x 값보다 낮은 값을 갖는다.
• 오른쪽 자식과 그 모든 하위 항목은 x 값보다 높은 값을 갖는다.
• 왼쪽 및 오른쪽 하위 트리도 이진 검색 트리여야 한다.

효율적인 노드 배치 구조를 가졌기 때문에 일반 이진트리보다 더 빠른 검색, 추가 및 삭제가 가능하게 됩니다! (정렬된 배열에서 이진 검색의 검색이 효율적)

 

🌱 참고 [w3schools] BST

DSA Binary Search Trees

 

 

---

 

문제에서 친절히 주어진 binary tree의 구조

# 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

 

✔ Answer

BST의 특징을 활용하여 재귀호출하는 방식으로 문제를 해결할 수 있습니다.

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
    	# 재귀함수 종료
        if root == None:
            return 0
        
        # rangeSumBST 재귀 호출
        # 크다면 오른쪽 tree무시 - 왼쪽 subtree 탐색
        if root.val > high:
            return self.rangeSumBST(root.left, low, high)
        # 작다면 왼쪽 tree무시 - 오른쪽 subtree 탐색
        if root.val < low:
            return self.rangeSumBST(root.right, low, high)
        
        # 범위 내에 있다면 더하기
        return root.val + self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high)

---

 

 

💬 늦게 시작한만큼 더 열심히 해야지! 앞으로도 킵고잉~