Leetcode230. 두 갈래 검색 트리에서 K번째 작은 요소

제목

사고방식 1: 중서를 이용하여 두루 훑어보다

BST를 중순으로 훑어보고 k까지 훑어보았을 때 결과를 기록합니다.효율을 더욱 높이기 위해 k번째를 찾았을 때 더 이상 귀속하지 않습니다.두 가지 방법(내가 자주 사용하는 것)이 있다. 하나는 귀환 함수를 귀환 유형이 있는 것으로 설정하고 귀환 값에 따라 계속 귀환할지 여부를 결정한다.2: 참조 매개변수 판단 설정

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        int res = 0, cnt = 0;
        inorder(root, res, k, cnt);
        return res;
    }
    int inorder(TreeNode* root, int& res, int k, int& i)
    {
        if(root == nullptr)
            return 0;
        if(!inorder(root->left, res, k, i))
        {
            i++;
            if(i == k)
            {
                res = root->val;
                return 1;
            }
            return inorder(root->right, res, k, i);
        }
        return 1;
    }
};

사고방식2: 왼쪽 나무의 노드 개수를 통계한다

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        int leftCount = count(root->left);
        if(leftCount == k - 1)
            return root->val;
        else if(leftCount > k - 1)
            return kthSmallest(root->left, k);
        else
            return kthSmallest(root->right, k - leftCount - 1);
    }
    int count(TreeNode* root)
    {
        if(!root)
            return 0;
        return 1 + count(root->left) + count(root->right);
    }
};