[LeetCode/Easy] 938. Range Sum of BST

1. Input

1) TreeNode root

2) int low

3) int high

 

2. Output

1) root에 있는 노드 값 중에서 [low, high] 범위 내의 값만 더한 결과를 반환

 

3. Constraint

1) 노드 수의 범위는 [1, 2*10^4]이다.

2) 1 <= Node.val <= 10^5

3) 1 <= low <= high <= 10^5

4) root내의 모든 노드 값에는 중복이 없다.

 

4. Example

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15 -> Output: 32

설명: [7,15]내의 노드 값은 10, 15, 7이 있으므로 세 수의 합인 32를 반환한다.

 

5. Code

1) 첫 코드(2023/06/06)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        int sum = 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        TreeNode c;
        while(!q.isEmpty()){
            c = q.remove();
            if(low<=c.val && c.val<=high){
                sum += c.val;
                if(c.left!=null)
                    q.add(c.left);
                if(c.right!=null)
                    q.add(c.right);
            } else if(c.val<low && c.right!=null)
                q.add(c.right);
            else if(high<c.val && c.left!=null)
                q.add(c.left);
        }
        return sum;
    }
}

- 16%, 78%

- 다른 사람들 풀이를 확인해보니 재귀함수를 이용한 쪽이 더 빨랐다.