2 분 소요

BST

문제

문제 링크

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

Example 1:

Input: root = [3,1,4,null,2], k = 1 Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3 Output: 3

Constraints:

  • The number of nodes in the tree is n.
  • 1 <= k <= n <= 104
  • 0 <= Node.val <= 104

Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

스스로 고민

접근법

  • BST 접근!
  • 문제에서 타겟 값이 있고 배열에서 타겟 값 번쨰로 낮은 값을 반환하면 된다.
  • 예를 들어서 [4,2,3,1] 가 있다고 한다면 k 값이 3이라고면 세 번째 로 작은 값인 3을 반환해주면 된다.

의사코드

  • 이전에 코드를 재활용했다.
  • 복습겸 의사코드를 작성하자면 inorder_traversal 함수를 만든 후 node 가 None 값이 될 때까지 재귀호출한다.
  • None이 되면 inorder_traversal(node.left) + [node.val] + inorder_traversal(node.right) 에서 재귀호출이 끝나고 빈리스트를 다음과 같이 반환한다. [] + [node.val] + inorder_traversal(node.right)
  • 그럼 현재 node 값이 있으니 node.val 값이 리턴 되고 inorder_traversal(node.right) 가 진행된다.
  • 이런 식으로 전체 value 값이 오름차순으로 정렬된다.
  • values 는 리스트 이므로 리스트 인덱스에 k 값에 -1 을 하면 끝!

    구현 코드

class Solution:

    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:

        def inorder_traversal(node):

            if node is None:

                return []

            return inorder_traversal(node.left) + [node.val] + inorder_traversal(node.right)

  

        values = inorder_traversal(root)

        return values[k-1]

시간 복잡도와 공간 복잡도

  • 시간 복잡도:

    • 주어진 코드는 BST를 중위 순회하면서 모든 노드 값을 리스트에 저장하고, 그 중에서 k번째 값을 반환한다.
    • 중위 순회는 BST의 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(N) 다. 여기서 N은 BST의 노드 수 다.
    • 중위 순회 후, k번째 값을 얻기 위해 리스트에서 해당 값을 찾는 작업은 O(1)에 수행된다.
    • 따라서 전체 시간 복잡도는 O(N) 다.

  • 공간 복잡도:

    • inorder_traversal 함수는 BST를 중위 순회하면서 노드 값을 리스트에 저장한다. 이 리스트의 크기는 BST의 노드 수에 비례하므로 O(N)의 공간을 사용한다.
    • 추가적으로 변수 values와 함수 호출 스택에 필요한 공간도 있지만, 이들은 입력 크기에 선형적으로 의존하므로 O(N)의 공간을 사용한다.
    • 따라서 전체 공간 복잡도는 O(N) 다.

회고 과정

  • 확실히 아는 게 많아야 써먹을 수 있는 게 많아지고 응용할 수 있는 폭도 넓어 진다고 생각했다.

다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 최종 회고

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:   
        stack = []

        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            
            root = stack.pop()
            k -= 1
            if k == 0:
                return root.val
            
            root = root.right

  • 시간 복잡도:

    • 주어진 코드는 BST를 중위 순회하면서 k번째로 작은 값을 찾는다.
    • 중위 순회는 BST의 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(N) 다. 여기서 N은 BST의 노드 수다.
    • 중위 순회 중에 k번째 값을 찾으면 바로 반환하므로, 일반적인 경우에는 k번만 노드를 방문한다.
    • 따라서 전체 시간 복잡도는 O(N) 다.

  • 공간 복잡도:

    • 주어진 코드에서 사용되는 스택(stack)은 BST를 중위 순회하기 위한 임시 공간이다. 스택에는 최악의 경우에는 BST의 높이에 비례하는 공간이 필요하므로, 스택의 크기는 O(log N)에서 O(N) 사이의 범위에 있다.
    • 추가적으로 변수 k와 root에 필요한 상수 공간이 있다.
    • 따라서 전체 공간 복잡도는 O(N) 다.

  • 다음 번에는 while 문으로 문제를 풀어봐야겠다.

댓글남기기

참고