腾讯精选50题(13)

230.二叉搜索树中第K小的元素
https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/
给定一个二叉搜索树,编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明:
你可以假设 k 总是有效的,1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:
腾讯精选50题(13)
示例2:
腾讯精选50题(13)
(1)二叉搜索树有个很重要的特点就是中序遍历是从小到大排列的,今天这题我们正好利用这一特点。如果我们按中序遍历将元素压入栈中,那么res[k-1] 就是第k小的元素了

class Solution {
public:
    vector<int> res;
    int kthSmallest(TreeNode* root, int k) {
        helper(root);
        return res[k-1];
    }
    void helper(TreeNode* root){
        if(root==NULL) return;
        helper(root->left);
        res.push_back(root->val);
        helper(root->right);
    }
    
};

(2)第二种方法其实是第一种的改进,我们设置一个计数器,初始为k,中序遍历一个元素减一,当计数器为0时就是我们所要找的值。

class Solution {
public:
    int res = INT_MAX;
    int count;
    int kthSmallest(TreeNode* root, int k) {
        count = k;
        inorder(root);
        return res;
    }
    void inorder(TreeNode* root){
        if(root==NULL) return;
        inorder(root->left);
        if(res!=INT_MAX) return;
        count--;
        if(count==0) res = root->val;
        inorder(root->right);
    }
};
上一篇:剑指 Offer 07. 重建二叉树


下一篇:Smali语法基础