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

0. 문제

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

1. 문제 설명

• BST의 루트가 주어지면 k번째로 작은 값을 찾으시오.

2. 문제 풀이

2.1. 접근법

• 중위순회를 하면서 말단 노드를 찾는다.
• 말단 노드를 찾으면 count + 1을 한다.
• count가 k와 일치하면 해당 노드가 k번째 작은 값이 된다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int count;
    int ans;
    public int kthSmallest(TreeNode root, int k) {
        count = 0;
        ans = 0;
        inorder(root, k);
        return ans;
    }
    public void inorder(TreeNode root, int k) {
        if (root == null || ans != 0) return;
        inorder(root.left, k);
        count++;
        
        if (count == k) {
            ans = root.val;
            return;
        }
        inorder(root.right, k);
    }
}

4. 결과