My 20ms C++ solution with O(logN) time and O(1) space


  • 1
    H
    class Solution {
        int ans;
        int count = 0;
    public:
        int kthSmallest(TreeNode* root, int k) {
            kth(root, k);
            return ans;
        }
           
        void kth(TreeNode* root, int k){
            if(count > k) return;
            if(root->left)  kth(root->left, k);
            count++;
            if(count > k) return;
            if(count == k) {
                ans = root->val;
                return;
            }
            if(root->right) kth(root->right,k);
            
        }
    };
    

    An implementation of DFS. It will print out the answer when the counter reaches k.


  • 1
    D

    I think it is O(k + logN), not O(logN).
    I wonder if it does exit a O(logN) solution.


  • 0
    H

    Yeah, I realized that. I think I can do some modification.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.