[Grind75-LeetCode] Kth Smallest Element in a BST JAVA

반응형

728x90

[Grind75-LeetCode] Kth Smallest Element in a BST - Medium

---

접근

• 중위 순회

---

풀이

BST, 이진 탐색 트리에서 K번째로 작은 요소를 찾아 반환하는 문제이다. 이진 탐색 트리이기 때문에 루트를 기준으로 작은 값은 왼쪽 큰 값은 오른쪽으로 나눠지기 때문에 그 점을 이용해 값을 찾으면 된다. 

 

기본적으로 K번째 작은 값을 찾아야 하기 때문에 왼쪽 서브트리의 작은 값을 기준으로 탐색을 시작해야 한다. 루트를 기준으로 왼쪽 맨 아래 서브트리부터 탐색을 시작해 해당 서브트리의 루트, 오른쪽 서브트리 순으로 탐색을 진행해야 한다. 맨 아래 왼쪽 서브트리가 가장 작은 값이고 그다음으로 작은 값이 해당 노드의 루트 그리고 그다음으로 작은 값이 오른쪽 노드인데 이 순회의 형태는 중위 순회와 동일하다. 중위 순회란 트리를 순회할 때 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리 순서로 순회를 하는 방법인데 이 문제에서 적합한 방법이다.

    private int count = 0;  
    private int result = 0; 

    public int kthSmallest(TreeNode root, int k) {
        inorder(root, k);
        return result;
    }

결과 값과 몇 번째로 작은지 체크를 할 변수를 전역으로 뒀다. 중위 순회 메서드를 통해 result에 값이 할당된다.

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

중위 순회 메서드이다. 노드가 비었다면 탐색을 종료한다. 더 이상 자식이 존재하지 않는 왼쪽 맨 아래 노드에 방문했을 경우 이다. 만약 아직 왼쪽 맨 아래 노드에 도달하지 못했다면 해당 노드의 왼쪽 서브트리에 메서드를 재귀 호출해 준다. 함수의 동작 방식 자체가 함수가 호출될 경우 함수 호출 스택에 쌓이게 되고 함수가 종료될 때 스택에서 제거되는 형태로 이미 함수 1이 호출되어 진행하는 중 다른 함수 2가 호출된다면 진행 중이던 함수 1은 중간에 호출된 함수 2가 종료되기 전까지 다음 작업이 수행되지 않는다. 그렇기 때문에 루트 노드가 inorder 메서드로 호출된 경우 루트 노드를 기준으로 모든 왼쪽 서브트리가 처리된 후 count++ 코드가 수행된다. 맨 아래 왼쪽 노드에 도착하게 되면 처리가 시작되고 해당 노드가 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 {
    private int count = 0;  
    private int result = 0; 

    public int kthSmallest(TreeNode root, int k) {
        inorder(root, k);
        return result;
    }

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