리트코드 - 230. Kth Smallest Element in a BST

리트코드 - 230. Kth Smallest Element in a BST

출처 - https://leetcode.com/problems/kth-smallest-element-in-a-bst/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

이진 탐색 트리의 루트와 정수 k가 주어질 때, 트리 노드의 모든 값 중에서 k번째로 작은 값을 (1부터 시작하는 인덱스로) 반환하세요.

 

의사코드

min = 정수의 최대값 count = 0 함수 k번째 작은 값 (노드 root, int k)     sortAscending(root, k) 함수     min 리턴 함수 sortAscending(노드 node, int k)     if (node == null)         return;     sortAscending(node의 left노드, k)     count = count +1     if (count == k)         min = node.val         sortAscending(node의 right노드, k)

 

풀이코드

class Solution {
    private int min = Integer.MAX_VALUE;
    private int count = 0;

    public int kthSmallest(TreeNode root, int k) {
        sortAscending(root,k);
        return min;
    }

    private void sortAscending(TreeNode node, int k) {
        if (node == null) {
            return;
        }
        sortAscending(node.left, k);

        count++;

        if (count == k) {
            min = node.val;
        }

        sortAscending(node.right, k);
    }
}

코드설명

이진탐색트리에 다시 중위순회를 적용하여 풀은 문제다. 이전문제

count하는 변수를 만들고, 최소값 변수를 만든다.

 

그리고 오름차순 정렬하는 메소드를 만들어서 재귀형태로 순환을 한다.

왼쪽 끝부터 오른쪽 까지 하나씩 차례로 순회하는 구조를 만들고, 제일 왼쪽에 도달했을 때 부터 count를 하기 시작한다.

그러면 각각 노드에 count가 하나씩 추가되어 지정된다.

 

왜냐하면, 제일 마지막 왼쪽 자식 노드는 자식 노드가 없기 때문에 sortAscending이 모두 null이기 때문.

그렇게 해서 정렬을 하고 min 값을 반환하면 정답이 된다.

 

노드를 사용하니까 런타임도 거의 0ms 에 가깝게 나오고, 메모리 사용 효율도 좋은 편이다.

확실히 다른 자료구조에 비해 빠른 편이다.

 

시간복잡도 - O(n)

공간복잡도 - O(log n) 최악의 경우 O(n)

 

문제를 풀며 생각한 흐름과 배운 점

이전문제 를 풀고 풀어서 그런가 생각보다 쉽게 풀었다.

코드가 더 깔끔하게 풀고 싶지만, 이전 문제에 거의 하루 이상 고민(..좌절?) 한것에 비해 간단하게 풀었기 때문에 만족한다.

 

class Solution {
    public int kthSmallest(TreeNode root, int k) {
      Stack<TreeNode> st = new Stack<>();
      
      while (root != null) {
          st.push(root);
          root = root.left;
      }
          
      while (k != 0) {
          TreeNode n = st.pop();
          k--;
          if (k == 0) return n.val;
          TreeNode right = n.right;
          while (right != null) {
              st.push(right);
              right = right.left;
          }
      }
      
      return -1; // never hit if k is valid
    }
}

stack을 이용한 방법도 있다.

재귀 대신에 while문을 이용해서 꽃잎 잎사귀 떼듯 k 값을 하나씩 떼주고 있다.

while문 안에 while문 쓰는것이 뭔가 불편하긴 하지만, 재귀적인 연산이 불가능 할 때는 stack을 이용해서 먼저 때려넣고 꺼내서 비교하는 방법도 있으니 참고해야겠다.

 

정리

이진트리 중위순회 이용하기