C++ solution using in order traversal


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

  • 0
    Z

    The idea is simply, but I think the time and space cost is not efficient, especially when k is small.


  • 8
    W

    The vector is unnecessary since we only need to find the kth value. An int is enough. This solution use less space and cost less time:

    void inorder(TreeNode* node, int& fid, int& k) {
        if (!node) return;
        inorder(node->left, fid, k);
        if (!k) return;
        fid = node->val;
        inorder(node->right, fid, --k);
    }
    
    int kthSmallest(TreeNode* root, int k) {
        int fid;
        inorder(root, fid, k);
        return fid;
    }

Log in to reply
 

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