BST의 K번째로 작은 요소

요구사항 정의

root이진 검색 트리의 와 정수가 주어 지면 트리에 있는 노드의 모든 값 중 가장 작은 값( 1-인덱스k )을 반환합니다.

풀이 생각

treeNode 를 구현하고

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int val) {
        this.val = val;
    }
}

초기값 설정

  private int kthSmallest = 0;
    private int count = 0;

재귀함수 구현

if (node == null || count >= k) {
            return;
        }
        
        inorderTraversal(node.left, k);
        
        count++;
        if (count == k) {
            kthSmallest = node.val;
            return;
        }
        
        inorderTraversal(node.right, k);

전체코드

lass TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int val) {
        this.val = val;
    }
}

public class Solution {
    private int kthSmallest = 0;
    private int count = 0;
    
    public int kthSmallest(TreeNode root, int k) {
        inorderTraversal(root, k);
        return kthSmallest;
    }
    
    private void inorderTraversal(TreeNode node, int k) {
        if (node == null || count >= k) {
            return;
        }
        
        inorderTraversal(node.left, k);
        
        count++;
        if (count == k) {
            kthSmallest = node.val;
            return;
        }
        
        inorderTraversal(node.right, k);
    }
}