LeetCode Top Interview 150) Kth Smallest Element in a BST

EBAB!·2023년 9월 7일
0

LeetCode

목록 보기
27/35

Question

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.

Constraints:

  • The number of nodes in the tree is n.
  • 1 <= k <= n <= 10^4
  • 0 <= Node.val <= 10^4
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:




보기 코드의 BST 구조를 가진 트리의 루트 노드 root와 정수 k가 주어집니다. 트리가 가진 값중 k번째로 작은 값을 반환하는 문제입니다

제가 생각한 코드는 다음과 같습니다.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = []

        while root != None:
            stack.append(root)
            root = root.left

        for _ in range(k-1):
            node = stack.pop()
            if node.right != None:
                node = node.right
                while node != None:
                    stack.append(node)
                    node = node.left
        return stack[-1].val
  • stack : 노드를 순회하기 위해 노드를 저장하는 리스트입니다.
    • 초기화는 while문을 통해 BST의 왼쪽 노드들을 저장했습니다.
  • BST구조상 stack의 가장 마지막 값이 트리의 최솟값입니다. 이런 방식을 k번 수행하여 k번째 최솟값을 찾습니다. 초기화를 하면서 최솟값을 찾았으니 for문k-1번 반복합니다.
    • 최솟값 노드의 상위 노드로 올라갑니다. 만약 오른쪽 노드가 존재한다면 해당 노드로 이동하고 다시 왼쪽 서브노드의 왼쪽 끝단까지 노드를 저장합니다.
      • 이렇게 stack의 마지막 노드값이 다음 최솟값으로 저장이 됩니다


BST의 구조 특징을 이용해 깊이 탐색을 했습니다.
쉽게 말해보자면 왼쪽값이 없을 때까지 탐색을 k번 하고 탐색이 끝난 시점의 값을 반환합니다.

우선 BST 구조이므로 최솟값은 가장 왼쪽의 노드입니다. 그리고 다음 최솟값은 상위 노드이고 다음 최솟값은 상위 노드의 오른쪽 노드를 탐색합니다. 이런 과정을 반복하게 됩니다.

profile
공부!

0개의 댓글

관련 채용 정보

Powered by GraphCDN, the GraphQL CDN