A naive solution with in-order travel, O(n), should have been much better with a lg(n) solution. Any comment is welcome.


  • 1
    S
    class Solution {
    public:
        int kthSmallest(TreeNode* root, int k) {
            
            vector<int> result;
            InOrder(root,result);
            return result[k-1];
            
            
        }
        void InOrder(TreeNode* root,vector<int>& result)
        {
            if(!root)
            return;
            InOrder(root->left,result);
            result.emplace_back(root->val);
            InOrder(root->right,result);
        }
    };

  • 0
    P

    lg(n) to me is not possible, since you dont know where k is, in the worst case, you will always have to go over the whole tree to find where kth node is, then it is never be able to reach logn(n)


Log in to reply
 

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