学步园

题目描述：

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

输入：

输入可能包含多个测试样例。
对于每个测试案例，输入的第一行为一个数n(0<n<1000)，代表测试样例的个数。
接下来的n行，每行为一个二叉搜索树的先序遍历序列，其中左右子树若为空则用0代替。

输出：

对应每个测试案例，
输出将二叉搜索树转换成排序的双向链表后，从链表头至链表尾的遍历结果。

样例输入：

1
2 1 0 0 3 0 0

样例输出：

1 2 3

自己写的测试用例都能过，代码提交之后一直RunTime Error，不知道原因

#include <unistd.h>

#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <stack>
#include <queue>

typedef unsigned int u_int32_t;
const u_int32_t array_size=1024;

typedef struct _TreeNode
{
    int value;
    struct _TreeNode *left_child;
    struct _TreeNode *right_child;    
}TreeNode;

int ReadLine(int fd,int *buff,u_int32_t size)
{
	int count = 0;
	char tmp;
	while(read(fd,&tmp,1)!=-1)
	{		
		if(tmp == '\n')
		{
			break;
		}
		if(tmp == ' ')
		{
		}
		else if(tmp >= '0'&&tmp <= '9')
		{
			*(buff+count) = tmp - '0';
			count++;
		}
		else
		{
			printf("Bad input\n");
		}	
	}
	return count;
}

TreeNode* ConstructTree(int *buff,u_int32_t size)
{
	if(buff==NULL || size==0)
	{
		return NULL;
	}
	std::stack<TreeNode*> tree_nodes;
	u_int32_t i = 0;
	TreeNode* root = NULL,*p = NULL;
	root = (TreeNode*)malloc(sizeof(TreeNode));
	root->left_child = NULL;
	root->right_child = NULL;
	root->value = *(buff+i);
	tree_nodes.push(root);
	i++;	
	while(i<size-2)
	{
		while(*(buff+i) !=0 && i < size)
		{
			p = (TreeNode*)malloc(sizeof(TreeNode));
			p->value = *(buff+i);
			p->left_child = NULL;
			p->right_child = NULL;			
			tree_nodes.top()->left_child = p;
			tree_nodes.push(p);
			i++;
		}		
		if(*(buff+i+1) ==0 && i < size-1)
		{
			i++;
			while(*(buff+i)==0 && i < size)
			{
				tree_nodes.pop();
				i++;
			}
			if(!tree_nodes.empty())
			{
				p = (TreeNode*)malloc(sizeof(TreeNode));
				p->value = *(buff+i);
				p->left_child = NULL;
				p->right_child = NULL;			
				tree_nodes.top()->right_child = p;
				tree_nodes.pop();
				tree_nodes.push(p);
				i++;				
			}
		}
		else
		{
			i++;
			p = (TreeNode*)malloc(sizeof(TreeNode));
			p->value = *(buff+i);
			p->left_child = NULL;
			p->right_child = NULL;			
			tree_nodes.top()->right_child = p;
			tree_nodes.pop();
			tree_nodes.push(p);	
			i++;			
		}
	}
	return root;
}

TreeNode* MakeDoubleLinkFromTree(TreeNode* root)
{
	std::stack<TreeNode*> tree_nodes;
	TreeNode *head = NULL,*tail = NULL;
	while(root || !tree_nodes.empty())
	{
		while(root)
		{
			tree_nodes.push(root);
			root = root->left_child;
		}
		if(!tree_nodes.empty())
		{
			root = tree_nodes.top();
			if(tail)
			{
				tail->right_child = root;
				root->left_child = tail;
				tail = root;
			}
			else
			{
				head = tail = root;
			}
			if(root->right_child)
			{
				tree_nodes.pop();
				root = root->right_child;
			}
			else
			{
				tree_nodes.pop();
				root = NULL;
			}
		}
	}
	return head;
}

void PrintDoubleLink(TreeNode *head)
{
	while(head)
	{
		printf("%d ",head->value);
		head = head->right_child;
	}
	printf("\n");
}

void DestructTree(TreeNode *head)
{
	TreeNode *next = NULL;
	while(head)
	{
		next = head->right_child;
		free(head);
		head = next;		
	}
}

int main(int argc,char** argv)
{
	u_int32_t n = 0,i = 0,real_size = 0;
	char n_char[5];
	memset(n_char,0,sizeof(n_char));
	int array[array_size] = {0}; 
	while(scanf("%u",&n)!=EOF)
	{
		n = 0;
		i = 0;
		while(*(n_char+i)!='\n')
		{
			n = n*10 + *(n_char+i) - '0';
			i++;
		}
		i = 0;
		while(i<n)
		{
			real_size = ReadLine(fileno(stdin),array,array_size);
			TreeNode* root = ConstructTree(array,real_size);			
			TreeNode* head = MakeDoubleLinkFromTree(root);
			PrintDoubleLink(head);
			DestructTree(head);
			i++;
		}
		memset(n_char,0,sizeof(n_char));
	}
	return 1;
}