[LeetCode] 938 Range Sum of BST

Description

Given the root node of a binary search tree, return the sum of values of all nodes with a value in the range [low, high].

Example 1:

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

Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 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.

---

풀이

• 이진탐색트리. DFS를 사용하여 탐색한다.
• 탐색하는 노드가 최대, 최소 범위 내에 있으면 합계(sum)에 더한다.
• 탐색하는 노드가 최소 숫자보다 적을 경우 해당 노드의 오른쪽 자식 노드를 탐색한다.
• 탐색하는 노드가 최대 숫자보다 크다면 해당 노드의 왼쪽 자식 노드를 탐색한다.
  
  

  ---

코드

이전 코드

/**
 * 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) {
        TreeNode rootNode = root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(rootNode);
        int sum = 0;

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.val >= low && node.val <= high) {
                sum += node.val;
            }
            if (node.left == null && node.right==null) {
                continue;
            } else if(node.left != null && node.right != null){
                queue.offer(node.left);
                queue.offer(node.right);
            } else if (node.left != null) {
                queue.offer(node.left);
            } else if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return sum;
    }
}

완성 코드

/**
 * 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) {
        TreeNode rootNode = root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(rootNode);
        int sum = 0;

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.val > low && node.val < high) {
                sum += node.val;
                if (node.left == null && node.right == null) {
                    continue;
                } else if (node.left != null && node.right != null) {
                    queue.offer(node.left);
                    queue.offer(node.right);
                } else if (node.left != null) {
                    queue.offer(node.left);
                } else if (node.right != null) {
                    queue.offer(node.right);
                }
            } else if (node.val <= low) {
                if (node.val == low)
                    sum += node.val;
                if (node.left == null && node.right == null) {
                    continue;
                } else if (node.right != null) {
                    queue.offer(node.right);
                }
            } else if (node.val >= high) {
                if (node.val == high)
                    sum += node.val;
                if (node.left == null && node.right == null) {
                    continue;
                } else if (node.left != null) {
                    queue.offer(node.left);
                }
            }
        }

        return sum;
    }
}