二叉搜索树的第k个结点

题目描述
给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

思路：中序遍历

二叉搜索树的中序遍历就是从小到大排列，
所以在中序遍历的过程中，设置一个计数器cnt，计到第k个就可以输出结果

递归版本：

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
private:
    int cnt = 0;
    TreeNode* res = NULL;
public:
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        if(pRoot != NULL){
            if(cnt < k)
                KthNode(pRoot->left,k);
            
            cnt++;
            if(cnt == k){
                res = pRoot;
            }
            
            if(cnt < k)
                KthNode(pRoot->right,k);
        }
        return res;
    }
};

非递归版本：

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
private:
    int cnt = 0;
    TreeNode* res = NULL;
public:
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        TreeNode* p = pRoot;
        stack<TreeNode*> s;
        while(p != NULL || !s.empty()){
            if(p){
                s.push(p);
                p = p->left;
            }else{
                p = s.top();
                s.pop();
                
                cnt++;
                if(cnt == k){
                    res = p;
                    break;
                }
                
                p = p->right;
            }
        }
        return res;
    }
};

最后

以上就是炙热咖啡豆为你收集整理的二叉搜索树的第k个结点的全部内容，希望文章能够帮你解决二叉搜索树的第k个结点所遇到的程序开发问题。

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