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.
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의 왼쪽 노드들을 저장했습니다.stack
의 가장 마지막 값이 트리의 최솟값입니다. 이런 방식을 k번 수행하여 k번째 최솟값을 찾습니다. 초기화를 하면서 최솟값을 찾았으니 for문
을 k-1
번 반복합니다.BST의 구조 특징을 이용해 깊이 탐색을 했습니다.
쉽게 말해보자면 왼쪽값이 없을 때까지 탐색을 k번 하고 탐색이 끝난 시점의 값을 반환합니다.
우선 BST 구조이므로 최솟값은 가장 왼쪽의 노드입니다. 그리고 다음 최솟값은 상위 노드이고 다음 최솟값은 상위 노드의 오른쪽 노드를 탐색합니다. 이런 과정을 반복하게 됩니다.