Kth Smallest Element in a BST

문제

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.

풀이

• 트리에 있는 노드 중에서 k번째 최솟값을 찾는 문제
• BST이므로 현재 노드보다 작은 값은 왼쪽, 큰 값은 오른쪽에 있다는 특징을 이용한다.
• inorder로 탐색하게 되는 경우, 오름차순으로 노드를 방문하게 된다.

수도 코드

def dfs(node):
	if node가 null이라면:
    	return
    
    dfs(node.left);
    // 최솟값 갱신
    dfs(node.right);

Solution(Runtime: 4ms)

import java.util.*;


class Solution {
    List<Integer> answer;

    public void dfs(TreeNode now) {
        answer.add(now.val);

        if (now.left == null && now.right == null) {
            return;
        }

        if (now.left != null) {
            dfs(now.left);
        }

        if (now.right != null) {
            dfs(now.right);
        }
    }


    public int kthSmallest(TreeNode root, int k) {
        answer = new ArrayList<>();
        dfs(root);
        Collections.sort(answer);
        return answer.get(k - 1);
    }
}

변경된 코드

class Solution {
    int K;
    int cnt;
    int kMin;

    public void dfs(TreeNode now) {
        if (now == null) {
            return;
        }

        dfs(now.left);
        cnt++;
        if (cnt == K) {
            kMin = now.val;
            return;
        }
        dfs(now.right);
    }


    public int kthSmallest(TreeNode root, int k) {
        K = k;
        dfs(root);
        return kMin;
    }
}

정렬을 할 필요가 없어져 4ms -> 0ms로 줄어들었다.