遍历
给定一棵二叉搜索树,请找出其中的第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;
};