Leetcode - 230. Kth Smallest Element in a BST

문제

주어진 BST에서 k 번째로 작은 값을 출력하라.

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

해결

BST이기 때문에 정렬이 되어있을것이고 inorder 순회를 하여 k번째 값을 출력하면 된다.

class Solution {
public:
    void dfs_inorder(TreeNode *root, int k, vector<int> &nums) {
        if (root == NULL && k < 0)
            return;
        if (root->left) dfs_inorder(root->left, k - 1, nums);
        nums.push_back(root->val);
        if (root->right) dfs_inorder(root->right, k - 1, nums);
        return;
    }
    int kthSmallest(TreeNode* root, int k) {
        vector<int> nums;
        dfs(root, k, nums);
        return nums[k - 1];
    }
};

추가로 dfs내에서 어떤 리턴값을 저장해야한다면, 어렵게 dfs함수의 리턴값으로 하지말고 그냥 매개변수 하나에 배열이나 벡터를 추가하자. 아래는 처음 풀었던 이상한 방식. 전역변수를 이상하게 사용함. 추천할수없는 방법!

class Solution {
public:
    int kth = 0;
    int ret = 0;
    void dfs(TreeNode *root, int k) {
        if (root == NULL && kth > k)
            return;
        if (root->left) dfs(root->left, k);
        kth++;
        if (kth == k) ret = root->val;
        if (root->right) dfs(root->right, k);
        return;
    }
    int kthSmallest(TreeNode* root, int k) {
        dfs(root, k);
        return ret;
    }
};