간단한 방법은 BFS 또는 DFS를 수행하여 모든 노드를 방문하면서 범위 내에 있는 값을 더하는 방법임
하지만 BST의 속성을 활용하여 효율적인 알고리즘 구현이 가능함
현재 노드의 값이 low보다 작을 경우, 왼쪽 서브트리를 확인할 필요가 없음
현재 노드의 값이 high보다 클 경우, 오른쪽 서브트리를 확인할 필요가 없음
이는 BST가 왼쪽 서브트리의 모든 값은 해당 노드의 값보다 작고, 오른쪽은 크다는 특성을 가지고 있기 때문에 가능
class Solution {
func rangeSumBST(_ root: TreeNode?, _ low: Int, _ high: Int) -> Int {
guard let root = root else { return 0 }
var ans = 0
if low <= root.val && root.val <= high {
ans += root.val
}
if low < root.val {
ans += rangeSumBST(root.left)
}
if high > root.val {
ans += rangeSumBST(root.right)
}
return ans
}
}
범위 내에 있는 값은 ans에 추가
low보다 해당 노드의 값이 작을 경우
→ 해당 노드의 왼쪽 서브트리는 low보다 작은 값임
→ 범위에 벗어나기 때문에 굳이 탐색할 필요가 없다.
high보다 해당 노드의 값이 클 경우
→ 해당 노드의 오른쪽 서브트리는 high보다 큰 값임
→ 범위에 벗어나기 때문에 굳이 탐색할 필요 없음
반복문 사용 예시
class Solution {
func rangeSumBST(_ root: TreeNode?, _ low: Int, _ high: Int) -> Int {
guard let root = root else { return 0 }
var ans = 0
var stack = [root]
while !stack.isEmpty {
let node = stack.removeLast()
if low <= node.val && node.val <= high {
ans += node.val
}
if let left = node.left, low < node.val {
stack.append(left)
}
if let right = node.right, node.val < high {
stack.append(right)
}
}
return ans
}
}
모든 노드가 low와 high 사이에 있는 경우 시간 복잡도가 O(n)이지만, 평균적으로 모든 노드를 탐색하는 것보다 효율적임
공간 복잡도는 스택 / 재귀 호출 스택에 대해 O(n)
예제 2
이진 탐색 트리의 루트가 주어졌을 때, 트리의 서로 다른 두 노드의 값 사이의 최소 절대 차이를 반환하세요.
예제 1
root = [4,2,6,1,3]
정답: 1
방법
트리를 순회하여, 배열을 만들고, 배열의 모든 쌍을 반복하여 최소 차이를 찾는 방법이 있음
하지만 시간 복잡도는 O(n^2)임.
더 나은 방법으로 배열을 정렬한 다음 인접 요소들을 반복하는 방법이 있음
정렬된 배열의 인접 요소들 사이에 있기 때문에 O(n * log n)가 소요됨
더 나은 방법은 중위 순회를 사용하는 것임.
BST에서 중위 순회를 사용하면, 노드를 정렬된 순서로 방문할 수 있음
이미 노드를 정렬된 순서로 얻을 수 있기 때문에 전체 시간 복잡도는 O(n)임
dfs 함수를 만들고, 중위 순회를 통해 정렬된 요소 values를 반환함
class Solution {
func getMinimumDifference(_ root: TreeNode?) -> Int {
var values: [Int] = []
func dfs(_ node: TreeNode?) {
guard let node = node else { return }
dfs(node.left)
values.append(node.val)
dfs(node.right)
}
dfs(root)
var ans = Int.max // 가장 작은 값을 가져와야 하기 때문
for i in 1 ..< values.count {
ans = min(ans, values[i] - values[i - 1])
}
return ans
}
}
시간 복잡도와 공간 복잡도는 O(n)입니다
BST의 속성을 이용하여 선형 시간 내에 값을 정렬된 순서로 얻을 수 있다
예제 3
이진 트리의 루트가 주어졌을 때, 해당 트리가 유효한 이진 탐색 트리인지 확인하세요.
유효한 BST의 정의는 다음과 같습니다
노드의 왼쪽 서브트리는 해당 노드의 값보다 작은 값을 가진 노드로 구성됩니다.
노드의 오른쪽 서브트리는 해당 노드의 값보다 큰 값을 가진 노드로 구성됩니다.
왼쪽 및 오른쪽 서브트리도 각각 유효한 이진 탐색 트리여야 합니다.
예제 1
root = [2, 1, 3]
정답: true
방법
재귀를 사용하여, node를 인자로 받고 트리가 BST인지 확인하는 함수 dfs를 만들기
왼쪽 서브트리의 모든 노드는 해당 노드의 값보다 작아야 하고, 오른쪽 서브트리의 모든 노드는 커야 함.
이는 두 개의 정수 small과 large를 사용하여 small < node.val < large가 성립하도록 할 수 있음
small과 large는 어떻게 업데이트 해야할까?
왼쪽 서브트리의 노드는 node.val보다 작아야 하므로 large = node.val로 업데이트 할 수 있음
오른쪽 서브트리의 노드는 node.val보다 커야 하므로 small = node.val로 업데이트 할 수 있음
root는 어떤 값이든 가능하기 때문에 small과 large에 대한 초기 값으로는 Int.min과 Int.max를 전달할 수 있음.
비어있는 트리는 기본적으로 BST가 맞음. -> 현재 노드가 null일 경우 true를 반환할 수 있음
class Solution {
func isValidBST(_ root: TreeNode?) -> Bool {
func dfs(_ node: TreeNode?, _ small: Int, _ large: Int) -> Bool {
guard let node = node else { return true }
if !(small < node.val && node.val < large) {
return false
}
let left = dfs(node, small, node.val)
let right = dfs(node, node.val, large)
return left && right
}
return dfs(root, Int.min, Int.max)
}
}
root는 어느 값이든 될 수 있기 때문에, 초기 small과 large의 책정은 양 극단의 끝 값으로 결정
해당 노드의 값이 small과 large 범위 내에 없다면 유효하지 않음
left를 탐색할 때는 해당 노드의 값보다 작은 값들로 구성되어야 하기 때문에 large를 해당 노드의 값으로 업데이트
right를 탐색할 때는 해당 노드의 값보다 큰 값으로 구성되어야 하기 때문에 small를 해당 노드의 값으로 업데이트
함수의 반환 조건이 && 연산이라는 것은 모든 서브트리도 BST여야 하는 것을 강제
반복문 예시
class Solution {
func isValidBST(_ root: TreeNode?) -> Bool {
guard let root = root else { return true }
var stack = [(root, Int.min, Int,max)]
while !stack.isEmpty {
let (node, small, large) = stack.removeLast()
if !(small < node.val && node.val < large) {
return false
}
if let left = node.left {
stack.append(left, small, node.val)
}
if let right = node.right {
stack.append(right, node.val, large)
}
}
return true
}
}
