230. Kth Smallest Element in a BST

https://leetcode.com/problems/kth-smallest-element-in-a-bst/

Kth Smallest Element in a BST - LeetCode

 

이진 트리의 노드와 정수 k가 주어졌을 때 k번째로 작은 value를 리턴하는 문제다.

 

가장 작은 값(left->left...)부터 순차적으로 재귀를 통해 탐색하며 값을 찾고, 그 값을 반환하면 된다.

 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int solve(TreeNode* node, int& k) {
        if (!node) {
            return -1;
        }

        int ret = solve(node->left, k);
        if (ret != -1) {
            return ret;
        }

        --k;
        return k == 0 ? node->val : solve(node->right, k);
    }
    
    int kthSmallest(TreeNode* root, int k) {
        return solve(root, k);
    }
};

 

Discuss봐도 나랑 차이 없는거 같은데 시간이 좀 오래걸리네..