Very simple binary-search solution in C++, quite efficient


  • 0
    class Solution {
    private:
        int countNodes(TreeNode* root)
        {
            if(!root) return 0;
            return 1+countNodes(root->left)+countNodes(root->right);
        }
    public:
        int kthSmallest(TreeNode* root, int k) 
        {
            int lCount = countNodes(root->left);
            if(lCount == k-1) return root->val;
            if(lCount >= k) return kthSmallest(root->left, k);
            else return kthSmallest(root->right, k-lCount-1);
        }
    };

  • 0

    Enclosing a constant space cost yet efficient in-order traversing solution here, a Morris Traversing.

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

Log in to reply
 

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