[LeetCode | Java | DFS/BFS 문제 풀이] 938. Range Sum of BST - Solution with Recursion Function

99클럽 | Begginer

938. Range Sum of BST

🏷 Topic : Tree Depth-First Search Binary Search Tree Binary Tree BFS DFS

Easy

---

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.

Constraints:

• The number of nodes in the tree is in the range [1, 2 * 104].
• 1 <= Node.val <= 105
• 1 <= low <= high <= 105
• All Node.val are unique.

---

✔ Solution with Recursion Function

(⚠ 이 Solution은 처음 혼자 풀어봤던 코드,

코테 스터디 온라인 모임에서 클럽장님께 피드백 받은 내용은 이 다음 코드블럭을 참고하세요.)

/**
 * 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 sumV (TreeNode nodeT, int l, int h, int sumBST) {
        if (nodeT.left != null) {
            sumBST = sumV(nodeT.left, l, h, sumBST);
        }
        if (nodeT.right != null) {
            sumBST = sumV(nodeT.right, l, h, sumBST);
        }

        int nV = nodeT.val;

        if (nV >= l && nV <= h) {
            sumBST += nV;
        }

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

        sumBST = sumV(root, low, high, sumBST);

        return sumBST;
    }
}

채점 결과

---

✔ Solution with Recursion(Edited version)

/**
 * 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 {
    int sumBST = 0;

    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root.left != null) {
            rangeSumBST(root.left, low, high);
        }
        if (root.right != null) {
            rangeSumBST(root.right, low, high);
        }

        if (root.val >= low && root.val <= high) {
            sumBST += root.val;
        }

        return sumBST;
    }
}

채점 결과

---

💥어떤 문제가 있었고, 어떤 시도를 했는지💦 & 어떻게 해결했는지👍

문제에 나온 Binary Tree Node부터 이해하는데 애를 먹었다.
마음을 가라앉히고 주석에 구현해 놓은 클래스를 참고하여 Binary Tree Node를 이해할 수 있었고
처음엔 Stack에 노드들을 넣어서 구현을 했는데 에러가 났다.
Stack이 용량을 많이 차지하는걸까? ArrayList는 좀 나을까?해서 ArrayList로 구현해도 마찬가지
결국 재귀함수로 코드를 쓰니 마침내 문제가 해결되었다.

• 풀이 과정은 LeetCode 링크 참고(👉 링크)

저녁에 99클럽 코딩 테스트 스터디 온라인 모임에서 자바 | 비기너 대표로 푼 문제를 발표했다.
클럽장님께서 피드백을 해 주셨는데 알고보니 재귀함수를 원래 있던 Solution클래스의 메서드 rangeSumBST()만으로도 충분히 구현할 수 있었다.
모임이 끝나고 다시 한번 더 클럽장님의 코드를 따라 써 보았다.
노드의 값들의 합을 담는 int sumBST를 정확히 어떻게 쓰셨었는지 기억이 안나서 그냥 Solution클래스 안에 전역변수로 선언해 주었는데 코드는 잘 돌아갔다.
메서드를 하나만 써도 된다니❗😮❗
눈이 번쩍 떠지는 신선한 충격이었다. 앞으로도 발표 자주 해야지!🤓🐱‍🏍

• 수정한 풀이 과정은 LeetCode 링크 참고(👉 링크)

💬 무엇을 새롭게 알았는지

• 클래스 안에 메서드 구현한 것을 같은 클래스 안의 다른 메서드에서 사용할 수 있구나.
• 재귀함수 구현하기 : 재귀함수를 메서드 하나만으로 구현할 수 있는 거였구나!
• Binary Tree Node의 기본 구조
• 트리 구조에 대해 찾아보고 정리해 보았다.
  ([Java 봐 | 자료 구조] 트리(Tree) 개념 정리 링크🔗)

---

📚 References(참고 자료)

[자료구조 Java] 이진 탐색 트리(Binary Search Tree) 개념 정리 + 자바로 구현하기
트리(Tree)의 개념과 종류 / Java 구현

[Java 봐 | 자료 구조] 트리(Tree) 개념 정리