LeetCode230. 二叉搜索树中第K小的元素：用时100%+内存99%（java+c++）（超高效的解法！！！！）

53 阅读 0 评论 35 点赞

我是靠谱客的博主热情酸奶，最近开发中收集的这篇文章主要介绍LeetCode230. 二叉搜索树中第K小的元素：用时100%+内存99%（java+c++）（超高效的解法！！！！），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/

题意

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

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

在这里插入图片描述

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

提示：

树中的节点数为 n 。
1 <= k <= n <= 104
0 <= Node.val <= 104

题解

本题使用常规思路，中序遍历记录节点的次序，当查找到第k个后结束遍历。

题解二

class Solution {
    int order=0;
    int result=0;
    boolean stop=false;
    public int kthSmallest(TreeNode root, int k) {
        inorderTraversal(root,k);
        return result;
    }

    private void inorderTraversal(TreeNode root,int k){
        if(null==root||order==k)return;//当查找到第k个，结束遍历
        inorderTraversal(root.left,k);
        if(++order==k)result=root.val;//此句还可能被执行，但result不再改变
        inorderTraversal(root.right,k);
    }
}

在这里插入图片描述

题解二

设置中序遍历返回值为布尔类型来标志是否结束遍历。
java代码

class Solution {
    int order=0;
    int result=0;
    public int kthSmallest(TreeNode root, int k) {
        inorderTraversal(root,k);
        return result;
    }

    private boolean inorderTraversal(TreeNode root,int k){
        if(null==root)return false;
        if(inorderTraversal(root.left,k))//若在子树中已经获得到，直接返回
            return true;
        if(++order==k){//获得到元素时，返回true
            result=root.val;
            return true;
        }
        return inorderTraversal(root.right,k);
    }
}

在这里插入图片描述
c++代码

class Solution {
public:
    int order=0;
    int result=0;
    int kthSmallest(TreeNode* root, int k) {
        inorderTraversal(root,k);
        return result;
    }
    
    bool inorderTraversal(TreeNode* root,int k){
        if(!root)return false;
        if(inorderTraversal(root->left,k))
            return true;
        if(++order==k){
            result=root->val;
            return true;
        }
        return inorderTraversal(root->right,k);
    }
};