Leetcode 230. 二叉搜索树中第K小的元素

问题描述

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明：

你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

Example

输入：root = [3,1,4,null,2], k = 1

输出：1

题目链接：230. 二叉搜索树中第K小的元素

思路

直接对 BST 进行中序遍历，然后输出第 k 个节点即可

代码

class Solution {
public:
    bool inorder(TreeNode* root, int& pre, int& k){
        if(root == NULL)
            return false;
        if(inorder(root->left, pre, k))
            return true;
        pre = root->val;
        if(--k == 0)
            return true;
        return inorder(root->right,pre, k);
    }
    int kthSmallest(TreeNode* root, int k) {
        int ans = INT_MIN;
        inorder(root, ans, k);
        return ans;
    }
};

执行结果：36 ms, 24.1 MB

赏

谢谢你请我吃糖果

支付宝

微信

• 本文作者： Phoenix
• 本文链接： https://phoenix500526.github.io/2020/06/24/Leetcode-230-二叉搜索树中第K小的元素/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！