[Leetcode] 230. Kth Smallest Element in a BST

Identifying the Problem

BST 구조 트리의 k번째로 작은 값을 구한다.

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

Organizing thoughts

Idea[1] : 중위순회를 하며, int vector에 node값 저장 후 , 정렬 , 앞에서 k-1 번째 수 리턴한다.

Idea[2] : 중위순회를 하며, k값을 빼가며 k가 1에 도달했을 때의 값을 리턴한다.

Sourcecode

##Idea[1]

class Solution {
public:
    vector<int> node;
    
    int kthSmallest(TreeNode* root, int& k) 
    {
        inorder(root);
        sort(node.begin(), node.end());
        return node[k-1];
    }
    
    void inorder(TreeNode* root)
    {
        if(root)
        {
            inorder(root->left);
            node.push_back(root->val);
            inorder(root->right);
        }
    }
};

 

##Idea[2] 정답코드 및 출처 

 

4 Lines in C++. - LeetCode Discuss

class Solution {
public:
    int kthSmallest(TreeNode* root, int& k) 
    {
        if (root) 
        {
            int x = kthSmallest(root->left, k);
            return !k ? x : !--k ? root->val : kthSmallest(root->right, k);
        }
        else return NULL;
    }
};

위 코드는 가독성이 떨어져 가독성이 좋은 코드를 찾아 해설해보았다.

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) { 
        return dfs(root, k);
    }
    int dfs(TreeNode* node, int& k) //int k 가 아니라 int& k 를 사용해 k값을 직접 변경한다.
    {
        if(!node) return NULL; //node가 없다면 null 리턴
        
        int l = dfs(node->left,k); //BST 구조이므로 중위순회
        
        if(k == 0) return l; //전달 받은 node->val 값 리턴, root로 다시 돌아올 때 k가 0인 상태가 된다.
        
        else if(k == 1) //k가 1일 때의 값이 k번 째 값이므로
        {
            k--; //k를 0으로 만들고, 정답 리턴
            return node->val;
        }
        else // k가 1보다 크면, 
        {
            k--; //k를 1 줄이고 (탐색했다는 흔적)
            int r = dfs(node->right,k); //오른쪽으로 중위순회를 이어나간다.
            if(k==0) return r; //오른쪽 탐색결과 정답을 찾았으면 정답 값 리턴
            else return NULL; //오른쪽이 빈노드거나 오른쪽을 탐색해도 못찾으면, null 리턴
        }
    }

};

Mistake

• tree도 하나의 dp 라고 생각하니 편하다.
• tree문제 풀 때, 최소단위의 트리를 가정해 생각해보면 수월하다.

New things learned

 

삼항연산자를 이중으로 사용했을 때 이해가 잘 안가 찾아보았다.

삼항연산자, 이중 삼항연산자