梁越

剑指62-二叉搜索树的第k个结点

0 人看过

遍历

题目描述

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

解法

第k小的结点,听起来很像是堆排序,对原二叉树进行调整应该是可以的,但是调整我忘了,而且我觉得用在这大材小用

我原来错误的想法:中序遍历,从最坐的结点开始,定义一个vector来保存比当前结点小的结点,但是这里有个问题,vector里的节点数可能会比k小,这时候确定不了倒数第k个结点

正确的做法:定义一个变量来控制遍历,因为是二叉搜索树,中序遍历的结果就是递增的,我居然忘记了这个性质,所以只要中序遍历第k个结点就行了

代码

/*
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, int k)
    {        
        if(!pRoot || k<1) return temp;

        if(count<k && pRoot->left) KthNode(pRoot->left, k);

        count++;
        if(count==k) 
        {
            temp=pRoot;
        }

        if(count<k && pRoot->right) KthNode(pRoot->right, k);

        return temp;
    }
private:
    TreeNode* temp=nullptr;
    int count=0;
};