938. Range Sum of BST

 

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

Range Sum of BST - LeetCode

 

youtu.be/3XmV2XzJrw0

/**
 * 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 {
    // 바이너리 서치
    // 현재 노드보다 작은값이 새로 들어오면, 왼쪽에 달고
    // 현재 노드보다 큰 값이 새로 들어오면, 오른쪽에 다는것
    
    // 바이너리 설치 탐색에서 진행여부 결정
    // base case: 더이상 진행을 못할 경우 return 0;
    
    // x x [low] x x x [high] x x x
    // 값이 범위안에 있으면 더해준다.
    // 현재 값이 로우보다 큰 경우, 오른쪽 진행
    // 현재 값이 하이보다 작은 경우, 왼쪽 진행
    
    int ans;
    
    public void dfs(TreeNode node, int low, int high) {
        if(node == null) return ;
        
        if(low <= node.val && node.val <= high)
            ans += node.val;
        
        if(low < node.val) dfs(node.left, low, high);
        if(node.val < high) dfs(node.right, low, high);
    }
    
    public int rangeSumBST(TreeNode root, int low, int high) {
        dfs(root, low, high);
        
        return ans;
    }
}

 

 

 

스택이용하여 BST로 하는것도 가능