[LeetCode] 938. Range Sum of BST (Day1)

 

- DFS(깊이 우선 탐색) 사용

public class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) {
            return 0;
        }

        int currentVal = (root.val >= low && root.val <= high) ? root.val : 0;

        int leftSum = rangeSumBST(root.left, low, high);
        int rightSum = rangeSumBST(root.right, low, high);

        return currentVal + leftSum + rightSum;
    }
}

 

DFS(깊이 우선 탐색)을 사용해서 재귀적 방법을 사용하였다.

DFS는 트리의 끝까지 탐색한다.

결국 전체를 찾아보게된다. O(n)이다.

 

 

 

Q. 전체 트리를 찾아볼 필요가 없다. 알다시피 트리의 왼쪽은 자신보다 작은 수, 오른쪽은 자신보다 큰 수가 온다.

그러므로 현재 위치한 root.val이 low보다 작으면 오른쪽 트리만 확인하면 되고, rootval이 high보다 높으면 왼쪽 트리만 확인하면 된다. 그리고 root.val이 low와 high 사이의 수라면 구해야 하는 수에 합하고 왼쪽, 오른쪽 트리 모두 구해야 한다. 

 

 

- Backtracking 알고리즘 사용

public class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) return 0;

        if(root.val < low){
            return rangeSumBST(root.right, low, high);
        } else if(root.val > high){
            return rangeSumBST(root.left, low, high);
        } else {
            return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
        }
	}
}

Backtracking 알고리즘을 사용했다. 이것도 O(n)이다.