// 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;

}