题目描述
给定一颗二叉搜索树，请找出其中的第k小的结点。例如，
5
/ \
3 7
/\ /\
2 4 6 8
中，按结点数值大小顺序第三个结点的值为4。
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x):val(x),left(NULL),right(NULL){}
};
void dfc(TreeNode *pRoot,vector<TreeNode*> &vec){
if(pRoot!=NULL){
dfc(pRoot->left,vec);
vec.push_back(pRoot);
dfc(pRoot->right,vec);
}
}
TreeNode* KthNode(TreeNode* pRoot, unsigned int k){
if(pRoot==NULL||k==0) return NULL;
vector<TreeNode*> vec;
dfc(pRoot,vec);
unsigned int len=vec.size();
if(k>len)
return NULL;
else
return vec[k-1];
}
int main(){
TreeNode n1(5),n2(3),n3(7),n4(2),n5(4),n6(6),n7(7);
TreeNode *root=&n1;
n1.left=&n2;
n1.right=&n3;
n2.left=&n4;
n2.right=&n5;
n3.left=&n6;
n3.right=&n7;
KthNode(root,3);
system("pause");
}