938. Range Sum of BST / TypeScript

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].

 

Example 1:

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.

Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 23
Explanation: Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23.

 

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

풀이 

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

const getSum = (root: TreeNode, low: number, high: number) => {
    if(!root)
        return 0;

    return getSum(root.left, low, high)
        + getSum(root.right, low, high) +
        (root.val >= low && root.val <= high ? root.val : 0);
}

function rangeSumBST(root: TreeNode | null, low: number, high: number): number {
    const sum = getSum(root, low, high);
    return sum;
};

 

• 왼쪽 서브트리와 오른쪽 서브트리의 합을 재귀적으로 계산
• 현재 노드의 값이 주어진 범위(low에서 high)에 포함되면 그 값을 더함