[LeetCode#938] Range Sum of BST

❒ Description

---

날짜	2024.09.25 (수)
레벨	Easy
제목	Range Sum of BST
링크	https://leetcode.com/problems/range-sum-of-bst/description/
자료구조	BST

 

 

 

 

 

❒ 문제 분석

---

트리에서 부모노드 보다 작은 노드는 왼쪽으로, 큰 노드는 오른쪽에 위치한다. 이번 문제에서는 가장 작은 값 low와

가장 큰 값 high를 제시해준다. 따라서 재귀 구조로 트리를 순회할 때 현재 노드의 값이 low 보다 작다면 오른쪽만

탐색하고, 현재 노드의 값이 high 보다 크다면 왼쪽만 탐색한다. 

• root < low : 오른쪽만 탐색
• root > high : 왼쪽만 탐색

 

 

 

 

❒ Solution

---

1. 트리의 특징을 통한 문제해결

public int rangeSumBST(TreeNode root, int low, int high) {
    return accNode(root, low, high);
}

public int accNode(TreeNode root, int low, int high) {
    if (root == null) return 0;
    int acc = 0;
    int target = root.val;
    if (target >= low && target <= high) {
        acc += target;
    }
    if (target < low) {
        acc += accNode(root.right, low, high);
    }
    if (target > high) {
        acc += accNode(root.left, low, high);
    }
}

 

 

 

 

 

---