⭐️ LeetCode 알고리즘 풀이 (with Python)

# Minimum Absolute Difference in BST

[Quetion]

LeetCode 530. Minimum Absolute Difference in BST

📌 접근법

[문제 이해]

• 트리에 있는 노드들 사이에서 최소 차이를 반환
• ex) [4, 2, 6, 1, 3]의 값을 가지는 트리가 있을 때, 2-1=1 이므로 1을 반환

특정한 두 값의 차이를 알기 위해서는 트리에 있는 모든 값을 탐색해야 한다고 생각했다.

그리고 탐색한 값을 정렬할 경우를 예시로 했을 때, [1, 2, 3, 4, 6] 이므로 두 값끼리 뺀 값 중 가장 작은 값으로 갱신해나가면 두 노드들 사이의 최소 차이를 반환할 수 있다고 판단했다.

그래서 생각한 흐름은 다음과 같다.

• DFS 방식으로 노드를 전부 탐색하여 리스트에 저장한다.
• 저장된 리스트 값을 정렬한다.
• 리스트 내 요소를 반복하는 첫번째 인덱스 포인터를 생성한다.
• 리스트의 길이까지 반복하며 요소 2개를 - 연산을 하고 작은 값만 저장한다.

💻 구현

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% 해당하는 결과

📝 Minimum Absolute Difference in BST 회고

• 시간복잡도를 계산했을 때, O(n)을 가지며, 루트 노드를 중간 순서에 탐색하는 중위 순회 방식으로 노드 데이터를 탐색했다.

• 탐색하는 함수 안에서 각 값들의 차이를 연산하고, 연산된 값 중 가장 작은 값만 반환하게 코드를 구성할 수 있다고도 생각했다. 그러나 링크드 리스트 형식의 트리 구조를 핸들링 하는 것이 아직은 어색해서 리스트를 활용했다.

• 성능적으로 크게 차이가 나지는 않을 것 같아서 탐색과정과 연산하여 결과 값을 반환하는 과정을 분리했다.
  추가적인 개선 사항은 잘 떠오르지 않아서 다른 솔루션들을 보았을 때, 대부분 inorder 방식으로 문제를 해결 하여 현재 코드와 비슷한 성능을 내는 것 같았다.
  

• 그래서 더 이상의 개선은 진행하지 않았지만, 다른 문제를 접하며 공부해보면서 좋은 아이디어가 떠오르면 더 좋은 성능을 내도록 개선 해봐야겠다.

---

# Kth Smallest Element in a BST

[Quetion]

LeetCode 230. Kth Smallest Element in a BST

📌 접근법

[문제 이해]

• 이진 검색 트리에서 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% 해당하는 결과

📝 Kth Smallest Element in a BST 회고

• 코드의 시간복잡도는 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의 방법으로 접근한 점이 이전에 작성한 코드와의 차이점인 것 같다. 가장 최소 값을 반환하면 되는 문제라서 왼쪽의 값이 무조건 오른쪽 보다 작다는 이진 검색 트리의 성격을 놓친 것이 아쉬웠다.

어떻게 접근하느냐에 따라 코드의 성능 차이가 나기 때문에 조금 더 접근 방법에 신중해져야겠다.