LeetCode 230. Kth Smallest Element in a BST 자바 문제 풀이

문제

Kth Smallest Element in a BST - LeetCode

문제 해결 방법

-이진 트리에서 K번째 노드를 출력받는 문제입니다.

-이진트리에서 작은수에서 큰수대로 출력하는 방법은 DFS-inorder입니다.

-DFS, inorder를 k만큼 반복한후 출력합니다

-다른 노드의 값이 필요하지 않으므로, 재귀함수가 아닌 그냥 반복문을 사용합니다.

-Follow up: 이진트리는 기본적으로 검색에 빠르고 수정이 느리므로, 이진트리말고 다른 데이터 스트럭쳐를 쓰는것이 좋습니다. 하지만 반드시 이진트리를 써야한다면,

1. 트리노드를 LinkedList가 아닌 Double Linked List로 구현
2. 값이 아닌 노드를 반환
3. 새로운 값을 insert
4. 이미 가지고 있는 노드에서 이전 노드의 값(새로운 값)을 출력

시간복잡도: O(n), 공간복잡도: O(n)

https://github.com/eunhanlee/LeetCode230..KthSmallestElementinaBST.git

public class Solution {

    /**
     * 이진 트리에서 k번째로 작은 값을 찾아 반환합니다.
     *
     * @param root 이진 트리의 루트 노드
     * @param k 찾을 k번째 값
     * @return k번째로 작은 값
     */
    public int kthSmallest(TreeNode root, int k) {
        int counter = 0;  // 현재까지 방문한 노드의 수를 저장
        int value = -1;   // 반환할 k번째로 작은 값, 찾지 못하면 -1을 반환

        if (root == null) {
            return value;  // 빈 트리인 경우 기본 값인 -1을 반환
        }

        Deque<TreeNode> stack = new LinkedList<>();  // 스택으로 사용할 덱 생성
        TreeNode current = root;

        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);  // 왼쪽 자식을 탐색하기 위해 스택에 현재 노드를 추가
                current = current.left;
            }

            current = stack.pop();  // 스택에서 가장 위의 노드를 팝하여 현재 노드로 설정
            counter++;
            value = current.val;  // 현재 노드의 값을 저장
            if (counter == k) break;  // 카운터 값이 k와 같다면 반복문 종료

            current = current.right;  // 오른쪽 자식으로 이동하여 탐색 계속 진행
        }

        return value;  // k번째로 작은 값 반환
    }
}