[Quetion]
- 트리에 있는 노드들 사이에서 최소 차이를 반환
- ex) [4, 2, 6, 1, 3]의 값을 가지는 트리가 있을 때, 2-1=1 이므로 1을 반환
특정한 두 값의 차이를 알기 위해서는 트리에 있는 모든 값을 탐색해야 한다고 생각했다.
그리고 탐색한 값을 정렬할 경우를 예시로 했을 때, [1, 2, 3, 4, 6] 이므로 두 값끼리 뺀 값 중 가장 작은 값으로 갱신해나가면 두 노드들 사이의 최소 차이를 반환할 수 있다고 판단했다.
그래서 생각한 흐름은 다음과 같다.
class Solution:
def getMinimumDifference(self, root):
r = []
self.inorder(root,r)
r.sort()
result = r[-1]
l=0
# -연산의 결과 중, 가장 작은 값을 갱신해나가며 리스트 길이까지 반복
for i in range(1,len(r)):
result = min(result, (r[i]-r[l]))
l+=1
return result
# DFS:중위순회 + 리스트에 노드 데이터 저장
def inorder(self,node,r):
r.append(node.val)
if node.left:
self.inorder(node.left,r)
if node.right:
self.inorder(node.right,r)
Runtime: 51ms | Memory: 18.6MB
LeetCode 코드 중 Runtime 90%, Memory 83% 해당하는 결과
시간복잡도를 계산했을 때, O(n)을 가지며, 루트 노드를 중간 순서에 탐색하는 중위 순회 방식으로 노드 데이터를 탐색했다.
탐색하는 함수 안에서 각 값들의 차이를 연산하고, 연산된 값 중 가장 작은 값만 반환하게 코드를 구성할 수 있다고도 생각했다. 그러나 링크드 리스트 형식의 트리 구조를 핸들링 하는 것이 아직은 어색해서 리스트를 활용했다.
성능적으로 크게 차이가 나지는 않을 것 같아서 탐색과정과 연산하여 결과 값을 반환하는 과정을 분리했다.
추가적인 개선 사항은 잘 떠오르지 않아서 다른 솔루션들을 보았을 때, 대부분 inorder 방식으로 문제를 해결 하여 현재 코드와 비슷한 성능을 내는 것 같았다.
그래서 더 이상의 개선은 진행하지 않았지만, 다른 문제를 접하며 공부해보면서 좋은 아이디어가 떠오르면 더 좋은 성능을 내도록 개선 해봐야겠다.
[Quetion]
- 이진 검색 트리에서 k번째 작은 값을 가지고 있는 노드 데이터 반환
- ex) k=1일 때, 이진 검색 트리에서 가장 작은 값을 반환
Minimum Absolute Difference in BST 문제에서 모든 노드의 데이터를 탐색하고 이를 정렬한 아이디어가 바로 떠올랐다.
탐색하고 리스트에 저장한 후 정렬하는 방법까지는 똑같이 접근하고, 오히려 리스트의 마지막 요소만 접근 하면 되기 때문에 아이디어를 떠올린 문제보다 더 간단하게 구현할 수 있었다.
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
r = []
self.inorder(root, r)
# 리스트 정렬 : O(log n)
r.sort()
# k번째 작은 값 = k-1번째 인덱스 값
return r[k-1]
# 중위순회
def inorder(self,node,r):
r.append(node.val)
if node.left:
self.inorder(node.left,r)
if node.right:
self.inorder(node.right,r)
Runtime: 53ms | Memory: 20.4MB
LeetCode 코드 중 Runtime 72%, Memory 53% 해당하는 결과
코드의 시간복잡도는 O(n)으로 중위순회 방식을 수행했을 때, 노드들의 개수 만큼 반복하기에 가장 높다.
리스트를 정렬하는 과정은 O(log n), k번째 만큼 작은 수에 접근할 때는 배열이기 때문에 O(1)의 시간복잡도를 가진다.
현재는 무조건 모든 노드를 탐색하기 때문에 O(n)의 시간이 들지만, 여러 솔루션들을 참고해 본 결과 이진 검색 트리의 성격을 활용하여 최대한 왼쪽의 하위 트리만 탐색하는 방법을 사용해서 평균 시간 복잡도 O(log n)으로 개선할 수 있다.
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
r = []
node = root
while True:
# 노드 왼쪽만 탐색, stack의 방법으로 노드 저장
while node is not None:
r.append(node)
node = node.left
# r == None : root 노드 없음
if not r:
break
# 가장 최근에 push한 노드 반환
result = r.pop()
k -= 1
# k == 0 : k번째 push한 k번째 작은 값
if k == 0:
return result.val
# 오른쪽 노드 탐색
node = result.right
Runtime: 53ms ---> 51ms
Memory: 20.4MB ---> 20.3MB
굳이 중위순회 함수를 따로 만들지 않고, while문으로 왼쪽 우선으로 탐색한 방법이다.
stack 자료구조를 활용하여 탐색한 노드를 저장해 나가고, 가장 위에 있는 노드를 POP하여 k번 POP했을 때 해당 노드의 값을 반환하는데, 확실히 왼쪽만 우선적으로 탐색하는 방법이라 기존 코드 보다 빠를 것이라 생각했다.
이진 검색 트리의 성격을 활용한 점, stack의 방법으로 접근한 점이 이전에 작성한 코드와의 차이점인 것 같다. 가장 최소 값을 반환하면 되는 문제라서 왼쪽의 값이 무조건 오른쪽 보다 작다는 이진 검색 트리의 성격을 놓친 것이 아쉬웠다.
어떻게 접근하느냐에 따라 코드의 성능 차이가 나기 때문에 조금 더 접근 방법에 신중해져야겠다.