.leetcode(938. Range Sum of BST)

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

 

1. 2022.02.19 시도

소요시간: 12분(3분 문제이해 및 구상, 9분 코딩, recursive), 2분(iterative)

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

// iterative
class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        
        int sum = 0;
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node == null) {
                continue;
            }
            
            
            if (low <= node.val && node.val <=high) {
                sum += node.val;
            }
            stack.add(node.left);
            stack.add(node.right);
        }

        return sum;
    }
}

풀이 접근 과정

합에 대한 정보를 리턴값으로 해야겠다고 생각했다. 주어진 메소드처럼 int형으로 하면 될것 같아 따로 메소드를 만들지 않았다.

모든 것을 순회하면서 범위에 맞으면 합하면 되겠다고 생각했다.

 

느낀점

• 여기서 좀 더 가미하면, recursion을 하거나 iterative할 때, 조건문을 부여하여 최소한으로 가게하는 방법이 있다. treeNode가 N으로 주어질 때, 어차피 O(N)이기에 따로 추가는 안했지만 그런것도 고려하면 좋은 포인트일 것이다.

 

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형