[LeetCode] 230. Kth Smallest Element in a BST

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

개요

1. 이진 검색 트리의 root 노드와 정수 k 가 주어진다.
   • 노드의 개수는 한 개
2. k번째 최소값을 구하라.

문제 해결 아이디어

• 이진 검색 트리는 모든 하위 트리가 왼쪽 노드의 값 < 루트 노드의 값 < 오른쪽 노드의 값이다.
  

🧐 왼쪽 리프 노드의 값부터 탐색하자

➡️ [최소값 - 두번째 최소값 - 세번째 최소값 ... - k번째 최소값] 순으로 값을 찾아나갈 수 있다.

의사 코드

1. 전역 변수 List 를 사용한다.
2. 현재 노드에 왼쪽 하위 노드가 있다면 왼쪽 하위 노드로 이동한다.
3. 하위 노드가 리프 노드라면 값이 삽입된다.
4. 다시 현재 노드로 돌아와, 이번에는 현재 노드의 값이 삽입된다.
   5 현재 노드에 오른쪽 하위 노드가 있다면 오른쪽 하위 노드로 이동한다.
5. 하위 노드가 리프 노드라면 값이 삽입된다.
6. list의 size가 k가 되면, 탐색을 중지한다.

void recursive(TreeNode 노드){
	if(list size == k) return;
    if(node.left != null) recursive(node.left);
    list.add(노드의 값);
    if(node.right != null) recursive(node.right);
}

결과

전체 코드 github 링크

다른 풀이

public int kthSmallest(TreeNode root, int k) {
    Stack<TreeNode> stack = new Stack<>();
    
    while (root != null || !stack.isEmpty()) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        // Decrease k since we've visited one element
        k--;

        if (k == 0) {
            break; // Break the loop as we've found the kth smallest element
        }
        root = root.right;
    }
    
    return root.val; // Return the value of the kth smallest element
    }

스택과 while문을 활용
1. [] ➡️ [5, 3, 2, 1]
root 노드의 왼쪽 노드들을 전부 스택에 집어넣는다.

• 1이 pop됨
• 1의 오른쪽 하위 노드가 없으므로 root == null이된다.

2. [5, 3, 2]
   root 노드가 null 이므로 스택이 유지된다.
   • 2가 pop됨
   • 2의 오른쪽 하위 노드가 없으므로 root == null이다
3. [5, 3]
   root 노드가 null 이므로 스택이 유지된다.
   • 3이 pop됨
   • 3의 오른쪽 하위 노드가 있으므로 root = 4번 노드가 된다.
4. [5] ➡️ [5, 4]
   root 노드가 4번 노드이므로 root 노드의 왼쪽 노드들을 전부 스택에 집어넣는다.
   - 4가 pop됨
   - 4의 오른쪽 하위 노드가 없으므로 root == null이된다.

나는 이진 검색 트리를 재귀로밖에 접근하지 못하겠어서, 재귀가 아닌 다른 풀이를 살펴봤다.
한단계 한단계 살펴보니까 이해되어서 다음번에는 한번 while문과 stack을 이용해서 풀이해봐야겠다.