230. Kth Smallest Element in a BST, 자바 풀이

[문제]
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.

Example 1:


Input: root = [3,1,4,null,2], k = 1
Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/?envType=study-plan-v2&envId=top-interview-150

/**
 * 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 {
    static List<Integer> list;
    public int kthSmallest(TreeNode root, int k) {
        list = new ArrayList<>();
        dfs(root);

        Collections.sort(list); // O(nlogN)

        return list.get(k - 1);
    }

    // 1,000,000

    static void dfs(TreeNode node) {
        if (node == null) {
            return;
        }

        list.add(node.val);

        dfs(node.left);
        dfs(node.right);
    }
}

// 주어진 BST(이진 탐색 트리)의 노드중 k번째로 작은 값을 찾아라!
// 각 부모노드의 자식 노드들을 순회하며 list에 추가한다.
// 순회한 노드가 null 인 경우, return 한다.
// 각 노드의 값들을 담은 list를 정렬한 후, k-1 번째 인덱스 값을 return 한다.