二叉搜索树的第k个结点

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

思路：

1、中序遍历并用vector保存每个节点，此时vector中节点的值是按序存放的，返回vector中第k个值；此方法空间复杂度为O(K),而且要遍历完所有节点。
2、优化，中序访问至第k个节点，且只保存第k个节点的值，此方法空间复杂度为O(1),只遍历K个节点

//方法1
class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        if (NULL == pRoot || k<=0)
            return NULL;
        
        vector<TreeNode*> vecVal;
        Inorder(pRoot, vecVal);
        return vecVal.size() < k ? NULL : vecVal[k-1];
    }
    
    void Inorder(TreeNode* pRoot, vector<TreeNode*> &vecVal)
    {
        if(NULL != pRoot->left)
        {
            Inorder(pRoot->left, vecVal);
        }
        vecVal.push_back(pRoot);
        if(NULL != pRoot->right)
        {
            Inorder(pRoot->right, vecVal);
        }
    } 
};


//方法2
class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        if (NULL == pRoot || k<=0)
            return NULL;
        
        TreeNode* res = NULL;
        int cur_num = 0;
        InorderFirstK(pRoot, res, cur_num, k);
        return res;
    }
    
    //cur_num一定是引用，不然结果不对
    void InorderFirstK(TreeNode* pRoot, TreeNode *&res, int &cur_num, int k)
    {
        if (cur_num > k)
            return;
        if(NULL != pRoot->left)
        {
            InorderFirstK(pRoot->left, res, cur_num, k);
        }
        if (k == ++cur_num)
        {
            res = pRoot;
            return;
        }
        if(NULL != pRoot->right)
        {
            InorderFirstK(pRoot->right, res, cur_num, k);
        }
    } 
};

最后

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

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