[LeetCode] 230. Kth Smallest Element in a BST - Java[자바]

링크

문제

이진 검색 트리의 root와 정수 k가 주어졌을 때, 트리에 있는 모든 노드의 값 중 k번째 작은 값(1-indexed)을 반환합니다.

풀이

중위 순위를 합니다.

class Solution {  
  
    // k번째로 작은 값을 탐색하기 위한 카운터 변수  
    private int count;  
    // k번째로 작은 값을 저장하는 변수  
    private int result;  
  
    public int kthSmallest(TreeNode root, int k) {  
        // 초기화  
        count = k;  
        traverseInOrder(root);  
        // k번째로 작은 값 return        
        return result;  
    }  
  
    // 중위순회  
    private void traverseInOrder(TreeNode node) {  
        // 현재 노드가 null 이면 순회 종료  
        if (node == null) {  
            return;  
        }  
  
        // 현재 node의 왼쪽 서브 트리 순회  
        traverseInOrder(node.left);  
  
        // 왼쪽 서브 트리 순회 후 현재 노드 검사  
        // 현재 노드가 k 번째 작은 값이면 result에 현재 노드의 값을 할당   
		if (--count == 0) {  
            result = node.val;  
            return;  
        }  
  
        // 현재 node의 오른쪽 서브 트리 순회  
        traverseInOrder(node.right);  
    }  
}

각 단계의 설명을 주석으로 달아놨습니다.