[1스4코2파] # 211 LeetCode 230. Kth Smallest Element in a BST

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (211차)
[4코1파] 2023.01.13~ (203일차)
[1스4코1파] 2023.04.12~ (114일차)
[1스4코2파] 2023.05.03 ~ (92일차)

Today :

2023.08.03 [211일차]
Tree
Kth Smallest Element in a BST

Kth Smallest Element in a BST

https://leetcode.com/problems/kth-smallest-element-in-a-bst/

문제 설명

binary search tree와 k가 주어졌을 때, 트리의 k번째로 작은 노드의 값을 return 한다.

문제 풀이 방법

"binary search tree" 기 때문에 root 기준 left node에 있는 값은 root의 val 값보다 작고 right node에 있는 값은 root의 val보다 크다는걸 생각하고 풀어야 함
stack을 사용해서 left 노드를 넣어주면서 while문을 돌고, left가 없으면 right를 serach 하면서 주어진 k를 -1씩 감쇠하고 k값이 0에 도달했을 때의 루트 노드의 val을 return 한다.

내 코드

# 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 = []
        cur = root

        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left

            cur = stack.pop()
            k-=1
            if k==0:
                return cur.val

            cur = cur.right

증빙

여담

아졸려