[3주차] 230. Kth Smallest Element in a BST

https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/?envType=study-plan-v2&envId=top-interview-150 

Kth Smallest Element in a BST - LeetCode

---

📝 문제

BST의 루트와 정수 자연수 k 가 주어진다. BST의 k 번쨰로 작은 수를 리턴하라.

 

🎈 풀이

중위순회를 돌면 작은 수 부터 탐색하게 되므로 일반적인 중위 순회에 조건식 하나만 추가하였다.

 

시간복잡도: O(n)

공간복잡도: O(n)

class Solution {
    int cnt = 0;
    
    public int kthSmallest(TreeNode root, int k) {
        return dfs(root, k, 0);
    }

    private int dfs(TreeNode node, int k, int target) {
        if (node == null) return target;
        
        target = dfs(node.left, k, target);
        
        cnt++;
        if (cnt == k) {
            target = node.val;
        }

        target = dfs(node.right, k, target);
        

        return target;
    }
}