力扣230-二叉搜素树的第k小元素-C++

一、运行结果

二、题目

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

示例 1：
输入：root = [3,1,4,null,2], k = 1
输出：1
示例 2：
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst

三、思路

按照二叉搜索树中序遍历有序的特点，对给出的二叉搜索树进行中序遍历，用一个变量count 记录当前遍历的结点是第几个结点，如果count == k，表示当前节点的值就是二叉搜索树中的第k 小值，用ans 存储，遍历到此即可，不用遍历完整棵树。

四、代码

class Solution {
public:
    int count = 0, ans; //count记录当前是第几个结点，ans记录结果
    int kthSmallest(TreeNode* root, int k) {
        inorder(root, k);
        return ans;
    }

    // 中序遍历
    void inorder(TreeNode* root, int k){
        if(root ==  NULL) return;
        inorder(root->left, k);
        count++;
        if(count ==  k){
            ans = root->val;
            return;
        }
        inorder(root->right, k);
    }
};

最后

以上就是积极过客为你收集整理的力扣230-二叉搜素树的第k小元素-C++的全部内容，希望文章能够帮你解决力扣230-二叉搜素树的第k小元素-C++所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。