[ATO] 54、二叉搜索树的第k个结点

题目描述

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

参考代码

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot, unsigned int &k)  // 这里一定要用 引用！！
    {
        TreeNode* pAns = nullptr;
        if(pRoot == nullptr || k <= 0)
            return pAns;
        
        pAns = KthNode(pRoot->left, k);
        
        if(pAns == nullptr){
            k--;
            if(k == 0)
                pAns = pRoot;
        }
        
        if(pAns == nullptr)
            pAns = KthNode(pRoot->right, k);
        
        return pAns;
    }

};

注意函数参数那里一定要用引用。其次，建议以后这种算法题的解法，写成两个函数实现。

最后

以上就是想人陪手链为你收集整理的[ATO] 54、二叉搜索树的第k个结点的全部内容，希望文章能够帮你解决[ATO] 54、二叉搜索树的第k个结点所遇到的程序开发问题。

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