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

// ConsoleApplication2.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "stdafx.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
#include<list>
#include<iterator>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;





struct TreeNode {
	char 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)
	{
		getData(pRoot);
		if (k <= 0) return NULL;
		if (k > qu.size()) return NULL;
		for (int i = 1; i < k; i++)
		{
			qu.pop();
		}
		return qu.front();
	}

	queue<TreeNode*> qu;
	void getData(TreeNode* T)
	{
		if (T == NULL) return;
		else
		{	
			getData(T->left);
			qu.push(T);
			getData(T->right);
		}
	}

	//序列化二叉树，前序创建二叉树
	int p = -1;
	TreeNode* Deserialize(char *str) {
		if (*str == NULL) return NULL; //str为空
		TreeNode *T = NULL;
		++p;
		if (p >= strlen(str)) return NULL; //超出str的范围
		if (str[p] == '#') return NULL; //str的值等于#
		T = new TreeNode(str[p]);
		T->left = Deserialize(str);
		T->right = Deserialize(str);
		return T;
	}
	void preOrder(TreeNode *T)
	{
		if (T == NULL) return;
		else
		{
			cout << T->val << "  ";
			preOrder(T->left);
			preOrder(T->right);
		}
	}

};

int main()
{

	//int num = 5;
	//char *ch = new char[num];
	//cout << "strlen(ch):" << strlen(ch)<<endl;
	//cout << endl;


	Solution so;
	TreeNode *T;
	int num = 5;
	char *str = "532##4##76##8##";
	T = so.Deserialize(str);
	cout << "创建二叉树成功！"<<endl;

	cout << "前序遍历二叉树：" << endl;
	so.preOrder(T);
	cout << endl;

	TreeNode *re = so.KthNode(T,8);
	cout << "result:" << re->val << endl;


	//so.getData(T);
	//cout << "qu 队列中的值：" << endl;
	//so.print();
	//cout << endl;


	return 0;
}