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

1. 문제

---

- 이진 검색 트리에서 k번째로 작은 값을 구해라

2. 의사코드

---

이번 문제도 이전에 풀었던 leetcode 530번 문제와 비슷했다. 재귀를 이용해 노드를 정렬하고 k번째 노드의 값을 출력하면 될 것 같았다. 530번 문제의 내용은 링크에서 https://rhdqors.tistory.com/107 확인 가능하다.

1. 변수 설정 (재귀, 정렬된 값 저장)
    Integer data = null;
    ArrayList<Integer> lists = new ArrayList<>(); // 우선 List를 이용해 정렬된 값을 저장시켜 본다

2. 재귀함수, 값 정렬
    public void 재귀(TreeNode node) {
        재귀(node.left); // 왼쪽 하위 트리 탐색
        data = node.val; // 각 노드의 값
        lists.add(data); // 각 노드 값 리스트에 추가
        재귀(node.right); // 오른쪽 하위 트리 탐색
    }

3. 실행
    재귀(root);
    return lists.get(k-1);

3. 시도

---

class Solution {
    Integer data = null;
    ArrayList<Integer> lists = new ArrayList<>();

    public int kthSmallest(TreeNode root, int k) {
        repeatForSort(root);
        return lists.get(k-1);
    }


    public void repeatForSort(TreeNode node) {
        if(node == null) return;
        repeatForSort(node.left);
        data = node.val;
        lists.add(data);
        repeatForSort(node.right);    
    }
}

list를 사용해서 그런지 메모리 사용량이 높았다. 처음에 생각했던대로 node를 정렬하며 k번째 노드의 값을 출력하면 더 빠를 것이라 생각한다.

class Solution {
    Integer data = null;
    int count = 0;

    public int kthSmallest(TreeNode root, int k) {
        repeatForSort(root, k);
        return data;
    }

    public void repeatForSort(TreeNode node, int i) {
        if(node == null) return;
        repeatForSort(node.left, i);

        count++;
        if(i == count) {
            data = node.val;
            return;
        }

        repeatForSort(node.right, i);    
    }
}

list를 없애고 매 실행마다 count를 업데이트했다. 실행마다 조금의 차이는 있지만 꽤 큰 개선이 된 것을 확인할 수 있다.