[LeetCode] 230. Kth Smallest Element in a BST - Java

Kth Smallest Element in a BST - LeetCode

 

문제

 

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

 

Example 1:

Input: root = [3,1,4,null,2], k = 1
Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

 

Constraints:

• The number of nodes in the tree is n.
• 1 <= k <= n <= 104
• 0 <= Node.val <= 104

 

Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

 

BST(이진탐색트리)의 root와 정수 k가 주어졌을 때, 트리의 모든 노드 값 중 k번째로 작은 값을 반환하는 문제이다.

 

---

 

내 풀이

 

BST의 중위 순회

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    static int count;
    static int answer;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        inorder(root);
        return answer;
    }

    public void inorder(TreeNode now){
        if(now == null) return;
        inorder(now.left);
        count--;
        if(count==0) {
            answer =  now.val;
            return;
        }
        inorder(now.right);
    }
}

 

앞에서 중위순회에 관한 문제를 풀었어서 쉽게 풀 수 있었다.

중위 순회를 하면 제일 값이 작은 노드부터 탐색하므로 count = k 로 초기화하고,

노드를 방문할 때마다 count 를 하나씩 줄여가며 0이 되었을 때 해당 노드의 값을 출력하는 형태로 코드를 짰다.

 

• 시간복잡도 : O(n)
• 공간복잡도 : 최악의 경우 O(n) / 평균 O(log n)

 

---

 

다른 사람의 풀이

 

스택 사용

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
}

같은 중위순회지만 재귀호출을 사용하지 않고 스택을 사용한 풀이이다.

• 시간복잡도 : O(n)
• 공간복잡도 : O(n) / 평균 O(log n)