230. Kth Smallest Element in a BST

문제

https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/

풀이

class Solution {
    int answer = 0;
    int count = 0;
    public int kthSmallest(TreeNode root, int k) {
        DFS(root, k);
        return answer; 
    }

    public void DFS(TreeNode node, int k) {
        if(node == null) {
            return;
        }

        DFS(node.left, k);
        if(++count == k) { 
            answer = node.val;
            return; // 부모 노드로 갱신됐으면 굳이 오른쪽 탐색할 필요 X (부모 노드보다 크니까)
        } 
        DFS(node.right, k);

        return;
    }
}

• BST의 경우 중위순회가 오름차순, 역중위순회가 내림차순 (오른쪽부터 탐색)