938. Range Sum of BST (BST의 범위 합)

Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

이진 탐색 트리의 root 노드와 두 정수 low과 high가 주어지면 포함 범위 [low, high]에 있는 값을 가진 모든 노드의 값 합계를 반환합니다.

예시 1:

입력: root = [10, 5, 15, 3, 7, null, 18], low = 7, high = 15
출력: 32
설명: 노드 7, 10, 15는 범위 [7, 15]에 있습니다. 7 + 10 + 15 = 32.

예시 2:

입력: root = [10, 5, 15, 3, 7, 13, 18, 1, null, 6], low = 6, high = 10
출력: 23
설명: 노드 6, 7, 10은 범위 [6, 10]에 있습니다. 6 + 7 + 10 = 23.

 

조건:

• 트리의 노드 수는 [1, 2 * 104] 범위 입니다.
• 1 <= Node.val <= 105
• 1 <= low <= high <= 105
• 모든 Node.val은 고유합니다.

정답:

public class Solution {
    public int RangeSumBST(TreeNode root, int low, int high) {
        if(root == null) 
        {
            return 0;
        }
        else if(root.val < low)
        {
            return RangeSumBST(root.right, low, high);
        }
        else if(root.val > high)
        {
            return RangeSumBST(root.left, low, high);        
        }

        return root.val + RangeSumBST(root.left, low, high) + RangeSumBST(root.right, low, high);
    }
}

해설: 

조건에 맞는 값을 찾을때까지 재귀하여 해당 값을 찾았을 때 값들을 더해주어 해결하였습니다.