[LeetCode] - M - 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

🌿 - 문제 설명

 Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

Binary Search Tree에서 K번째 수를 찾는 것이다.

 

📌 - 풀이

1. 중위순회를 하면 해당 값이 정렬되어 있으므로, 전위 순회를 하면서 k번째에 해당하는 값을 출력하면 됨
2. 중위순회를 하면서 k번째와 result값이 같을 때까지 result를 1씩 더해주고 k와 result가 같으면 해당 값을 출력해준다

 

🔥 - Java 코드

/**
 * 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 result = 1;
    int ans = 0;
    public int kthSmallest(TreeNode root, int k) {
        inorder(root,k);
        return ans;
    }

    void inorder(TreeNode node, int k){
        if(node == null){
            
            return;
        }
        
      
        inorder(node.left, k);
        if( k == result){
            ans = node.val;
            return;
        }else{
            result++;
        }

        inorder(node.right,k);

        
    }

}