리트코드) 938. 이진 탐색 트리(BFS) 합의 범위(자바)

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

문제 : 이진 탐색 트리(BFS)가 주어질 때 low 이상 high 이하 값을 지닌 노드의 합을 구하라

입출력1

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

입출력2

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

1. 브루트 포스 탐색

   트리를 한바퀴 돌며 범위에 속하면 합하기

   class Solution {
    int low;
    int high;
    int sum=0;
    public int rangeSumBST(TreeNode root, int low, int high) {
      if(root == null) {
          return 0;
      }
      this.low = low;
      this.high = high;
      calc(root);
      return sum;
    }
    public void calc(TreeNode tree) {
      if(tree != null) {
          if(tree.val >= low && tree.val <= high) {
              sum += tree.val;
          }
          calc(tree.right);
          calc(tree.left);
      }
    }
   }
   

2. dfs 가지치기로 필요한 노드 탐색
   • 정렬되어 있는 특성을 이용하여 값이 low보다 작으면 왼쪽을 탐색하고
     high보다 크면 오른쪽을 탐색한다.

   • 마지막 경우에 도달한다면 범위에 있다고 판단하여 모든 결과를 합산하여 반환한다. ``` class Solution { int low; int high; public int rangeSumBST(TreeNode root, int low, int high) { if(root == null) { return 0; } this.low = low; this.high = high; return calc(root); } public int calc(TreeNode tree) { if(tree == null) { return 0; } if(tree.val < low) { return calc(tree.right); } if(tree.val > high) { return calc(tree.left); }

     // 여기까지 도달 했다면 범위내에 있다고 판단, 모든 결과를 합산하여 반환 return tree.val + calc(tree.right) + calc(tree.left);

   } } ```

3. 반복 dfs
   • 재귀 -> 반복
   • 반복으로 하면 실행 속도가 재귀에 비해 조금 더 빨라진다.

     import java.util.*;
     class Solution {
      public int rangeSumBST(TreeNode root, int low, int high) {
        if(root == null) {
            return 0;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        int result = 0;
        while(!stack.isEmpty()) {
            TreeNode tree = stack.pop();
            if(tree.val > low) {
                if(tree.left != null) {
                    stack.push(tree.left);
                }
            }
            if(tree.val < high) {
                if(tree.right != null) {
                    stack.push(tree.right);
                }
            }
     
            if(tree.val >= low && tree.val <= high) {
                result += tree.val;
            }
        }  
        return result;
      }
     }
     

4. 반복 bfs
   • 스택 -> 큐

     import java.util.*;
     class Solution {
      public int rangeSumBST(TreeNode root, int low, int high) {
        if(root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int result = 0;
        while(!queue.isEmpty()) {
            TreeNode tree = queue.poll();
            if(tree.val > low) {
                if(tree.left != null) {
                    queue.add(tree.left);
                }
            }
            if(tree.val < high) {
                if(tree.right != null) {
                    queue.add(tree.right);
                }
            }
     
            if(tree.val >= low && tree.val <= high) {
                result += tree.val;
            }
        }  
        return result;
      }
     }
     

참고문헌 : 102가지 알고리즘 문제 풀이로 완성하는 코딩테스트 자바 알고리즘 인터뷰 556p