[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]内容请搜索靠谱客的其他文章。