LeetCode 230 Kth Smallest Element in a BST 풀러가기

문제

BST(Binary Search Tree) 와 k 가 주어진다.

BST 에서 k번째로 작은 수를 구해라.

문제 분석

첫번째 시도 (성공)

BST 이기에 dfs를 해서 왼쪽 부터 탐색하면 가장 작은 값을 알 수 있다.

그래서 왼쪽 노드를 탐색하고, 더 이상 왼쪽이 없을 때 return 하도록 하였다.

그리고 이렇게 왼쪽 탐색이 끝났을 때 자기 자신 숫자를 세면 된다.

이때 count++를 하였다.

그리고 이 count가 k 인덱스와 같아지면 answer에 담고 dfs 탐색을 더이상 하지않도록 구현했다.

코드

class Solution {
    TreeNode pre = null;
    int count = 0;
    int target = 0;
    int answer = 0;

    public int kthSmallest(TreeNode root, int k) {
        target = k;
        dfs(root);
        return answer;
    }

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

        dfs(node.left);
        count++;
        if(count == target){
            answer = node.val;
            return;
        }
        pre = node;
        dfs(node.right);
    }
}

결과 : 성공

Runtime

Memory

DFS 탐색을 했더니, 확실히 빨랐다. 더이상 탐색을 하지 않도록 if문을 넣은 게 좋았던 것 같다.