[Binary Tree][Medium] 230. Kth Smallest Element in a BST

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

 

Q. 주어진 binary search tree에서 k 번째로 작은 원소를 찾아 반환하라. 

 

Solution 

 k 가 tree의 원소 수 보다 작은 것이 문제에서 보장되므로, 예외처리는 필요 없다. 

 또한 inoder traverse의 결과가 오름차순 정렬이라는 것도 알고 있다. 

 

 따라서 inorder traverse하면서 k번째를 check 한다. 

 

    void inorder_BT(TreeNode* node, int k, int& idx, int& ret)
    {
        if(node == NULL)    return;
        if(idx >= k)        return;

        inorder_BT(node->left, k, idx, ret);

        ++idx;
        if(idx == k)        ret = node->val;

        inorder_BT(node->right, k, idx, ret);
    }
public:
    int kthSmallest(TreeNode* root, int k)
    {
        int ret = -1;
        int idx = 0;
        inorder_BT(root, k, idx, ret);
        return ret;
    }

 

 

결과.