230. Kth Smallest Element in a BST Leet Code 문제 풀이

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: 
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Example 1:

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

Example 2:

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

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

문제 해설 : 

1. Indorder 중위 순회를 통해서 BST 특성을 이용하여 순차적으로 가장 적은 숫자를 찾는다.

2. Vector에 가장 작은 숫자를 저장한 후, 답 출력시에 k-1 번째 배열의 값을 리턴

 

중위 순회 :

현재 노드의 왼쪽 노드를 먼저 방문하고 그 후 현재 노드 방문, 마지막으로 오른쪽 노드를 방문 한다. 

재귀 함수를 통해서 방문을 하게 될 경우, 가장 왼쪽 아래 노드로 계속해서 

재귀함수를 호출하게 된다. 그런 후, 가장 작은 노드의 값을 백터에 저장한 후,

중간노드로 다시 복귀 한다. 중간 노드의 값을 저장 그리고 오른쪽 노드 위치로 재귀함수를 수행.

같은 방법으로 왼쪽->현재->오른쪽 노드 방향으로 반복하게 된다. 

 

Binary Search Tree의 경우 자신의 왼쪽 자식 노드가 부모 노드의 값보다 작으며,

오른쪽 자식의 경우 부모노드의 값보다 큰 성질을 이용하여 문제를 푼다.

 

* ... 재귀함수를 새로 만들어서 수행하는 방법을 몰라 While 문으로 중위 순회를 시도해보려다가.. 실패... 

 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
  
public:
    vector<int> vec;
    void inorder(TreeNode *root){
        if(!root) return;
        inorder(root->left);
        vec.push_back(root->val);
        inorder(root->right);
    }
    int kthSmallest(TreeNode* root, int k) {
        inorder(root);
        return vec[k-1];
    }
};