BST中第k小的数

下面代码的重点是两个private变量。需要注意的是,在kthSmallestCore里面不能声明和结果有关的变量,否则由于递归的性质,最终的结果会被覆盖掉。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    int count = 0;
    TreeNode* res;
public:
    int kthSmallest(TreeNode* root, int k) {
        if(root == nullptr || k == 0)
            return 0;
        kthSmallestCore(root, k);
        return res->val;
    }
    
    void kthSmallestCore(TreeNode* proot, int k)
    {
        if(proot == nullptr)
            return;
        kthSmallestCore(proot->left, k);
        if(++count == k)
        {
            res = proot;
            return;
        }
        kthSmallestCore(proot->right, k);
    }
};

一个更高效的算法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    int count = 0;
    TreeNode* res;
public:
    int kthSmallest(TreeNode* root, int k) {
        if(root == nullptr || k == 0)
            return 0;
        res = nullptr;
        kthSmallestCore(root, k);
        return res->val;
    }
    
    void kthSmallestCore(TreeNode* proot, int k)
    {
        if(proot == nullptr)
            return;
        
        if(res == nullptr) // ##################################
            kthSmallestCore(proot->left, k);
        if(++count == k)
        {
            res = proot;
            return;
        }
        if(res == nullptr) // ##################################
            kthSmallestCore(proot->right, k);
    }
};

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

10 − 7 =

75 + = 80