leetcode 938, Range Sum of BST

들어가는 말

BST가 주어졌을 때, low와 high 사이에 있는 값들을 모두 더해서 리턴하는 문제다.

코드 설명

• 첫 번째
  트리를 전부 돌아서 그 값을 set에 넣고 set을 탐색하는 방식을 사용했다. 하지만, 문제를 푸는데 굳이 set이 필요하지는 않다.
• 두 번째
  BST를 돌면서 만일 해당 값이 low와 high 사이에 있다면 값을 더해주는 방식을 이용했다. 첫 번째 방식과 다르게 set을 이용할 필요가 없다.

1. 정답인 answer는 전역 변수로 두고 DFS를 호출한다.
2. 만일 현재 노드의 값이 low와 high 사이라면 그 값을 answer에 더한다.
3. 만일 노드의 자식 노드가 왼쪽과 오른쪽 모두 없다면 return을 한다.
4. 만일 왼쪽 노드가 존재하다면 왼쪽 노드를 탐색한다.
5. 만일 오른쪽 노드가 존재한다면 오른쪽 노드를 탐색한다.

class Solution {

    public int answer;

    public int rangeSumBST(TreeNode root, int low, int high) {
        answer = 0;
        DFS(root, low, high);
        
        return answer;
    }

    public void DFS(TreeNode node, int low, int high){

        if(node.val >= low && node.val <= high){
            answer += node.val;
        }

        if(node.left == null && node.right == null){
            return;
        }
        
        if(node.left != null){
            DFS(node.left, low, high);
        }

        if(node.right != null){
            DFS(node.right, low, high);
        }

        
    }
}

솔루션

BST는 새로 넣을 노드가 기준이 되는 노드보다 작을 경우 왼쪽에 클 경우 오른쪽에 넣는다. 그러므로 굳이 왼쪽 노드가 존재하면 왼쪽으로 가고 오른쪽 노드가 존재하면 오른쪽으로 가는 것보다 val을 기준으로 val이 low보다 크면 왼쪽으로 움직이고(low가 더 작기 때문에 val의 왼쪽에 있을 것) high보다 작으면 오른쪽으로 움직이는 게(high가 더 크기 때문에 val의 오른쪽에 있을 것) 나을 수도 있다.

class Solution {

    public int answer;

    public int rangeSumBST(TreeNode root, int low, int high) {
        answer = 0;
        DFS(root, low, high);
        
        return answer;
    }

    public void DFS(TreeNode node, int low, int high){
        if(node != null){
            if(node.val >= low && node.val <= high){
                answer += node.val;
            }
            if(low < node.val){
                DFS(node.left, low, high);
            }
            if(node.val < high){
                DFS(node.right, low, high);
            }

        }

        
    }
}