[leetCode] Kth Smallest Element in a BST

BST의 K번째로 작은 요소

Kth Smallest Element in a BST - LeetCode

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

 

예시 1:

입력: root = [3,1,4,null,2], k = 1
 출력: 1

예 2:

입력: root = [5,3,6,2,4,null,null,1], k = 3
 출력: 3

 

제약:

• 트리의 노드 수는 입니다 n.
• 1 <= k <= n <= 10^4
• 0 <= Node.val <= 10^4

---

문제풀이

/**
 * 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 {
    public int kthSmallest(TreeNode root, int k) {
        ArrayList<Integer> arr=new ArrayList<>();
        inorder(root,arr);
        return arr.get(k-1);
    }
    public static void inorder(TreeNode root,ArrayList<Integer> arr){
        if(root==null){
            return;
        }
        inorder(root.left,arr);
        arr.add(root.val);
        inorder(root.right,arr);
    }
    
}

이진트리의 최소 조건 3가지는 

1. 자식노드는 최대2개를 갖는다.
2. 왼쪽 자식노드는 부모노드보다 값이 작아야한다.
3. 오른쪽 지식노드는 부모노드보다 값이 커야한다.

문제는 이진트리의 조건을 충족하고 있습니다 그리하여 BST 순회방법중 하나를 선택하여 배열에 값을 저장하고 k번째 값을 추출하여 문제를 해결하려고 생각했습니다.

이진트리를 순회하는 방법은 3가지가 있습니다.

1. preorder(전위순회) 루트 노드에서 시작해서 노드-왼쪽 서브트리-오른쪽 서브트리 순으로 순회하는 방식입니다 (1,2,4,5,3)
2. inorder(중위순회) 루트 노드에서 시작해서 왼쪽 서브트리-노드-오른쪽 서브트리 순으로 순회하는 방식입니다.(4,2,5,1,3)
3. postoreder(후위순회) 루트 노드에서 시작해서 왼쪽 서브트리-오른쪽 서브트리-노드 순으로 순회하는 방식입니다. (4,5,2,3,1)

중위순회방법을 사용하여 arr에 값을 저장하면 최소값부터 차례대로 값을 저장 할 수 있어서 중위순회방법을 사용하였습니다.

예1) [1,2,3,4,5,6]

예2) [1,2,3,4]

arr.get(k-1)의 값을 반환하면 k번째로 작은 요소를 추출할 수 있습니다.

BST의 시간복잡도는 평균 O(log n)이고 최악의 경우의 수에 일 때 O(n)까지 걸릴 수 있습니다.