My 19ms binary search method, beats 100% submission!


  • 0
    X

    ...
    class Solution {
    public:

    int dfs(TreeNode* root){
        if(!root) return 0;
        return 1+dfs(root->left)+dfs(root->right);
    }
    
    int kthSmallest(TreeNode* root, int k) {
    
        int num=dfs(root->left);
        while(k!=num+1){
            if(k>num+1){
                root=root->right;
                k=k-num-1;
            }else if(k<num+1)
                root=root->left;
                
            num=dfs(root->left);
        }
        return root->val;
    }
    

    };
    ...


Log in to reply
 

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