[BinaryTree][Medium] 230. Kth Smallest Element in a BST

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

 

주어진 tree에서 k 번째로 작은 값을 찾아 반환하라. 

 

2진트리에서 InOrder traverse가 기본적으로 정렬을 의미함을 이해 한다. 

 

따라서 InOrder traverse했을 때, k 번째로 접근하는 node 값을 찾으면 된다. 

 

코드 

bool kthSmallestInOrder(TreeNode* node, int& k, int& outValue)
{
    if (node == nullptr)
        return false;

    if (kthSmallestInOrder(node->left, k, outValue))
        return true;

    --k;
    if (k == 0)
    {
        outValue= node->val;
        return true;
    }

    if (kthSmallestInOrder(node->right, k, outValue))
        return true;

    return false;
}

int kthSmallest(TreeNode* root, int k)
{
    if (k <= 0)	return 0;

    int ret = 0;
    kthSmallestInOrder(root, k, ret);
    return ret;
}

 

결과