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

내 initial idea는 사실 그냥 모든 node val 다 넣어서 그 중에서 k번째로 제일 작은 node val을 뽑는 것이었다.

하지만 그러면 아주 불필요한 부분들이 생긴다. 첫번째는 처음부터 끝까지 모든 tree node를 다 돌아야한다는 점, 두번째로는 additional array를 만들어야한다는점, 세번째는 그 array를 돌아야한다는 점이다.

Solution

✅ binary search tree이기 때문에 트리의 가장 left는 최소 숫자이다.
✅ 그래서 맨 왼쪽부터 하나씩 recursively 확인하면 된다.

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        n = 0
        stack = []
        
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            
            root = stack.pop()
            n += 1
            if n == k:
                return root.val
            
            root = root.right

Better version?

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = []
        
        while True:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if k == 0:
                return root.val
            root = root.right

변수 n을 만들어서 굳이 하나씩 더해주고 k와 비교해주는 것이 아닌, 하나의 노드를 돌때마다 k에서 1씩 빼주고 0이랑 같을때의 노드를 리턴하면 된다.

생각해볼 포인트

while 안의 리턴에서 무조건 값을 리턴할 수 밖에 없는 함수이다. 무조건 1 <= k <= n <= 104 라는 조건이 있기 때문이다,