【剑指offer】题目1385：重建二叉树

题目描述：

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并输出它的后序遍历序列。

输入：

输入可能包含多个测试样例，对于每个测试案例，

输入的第一行为一个整数n(1<=n<=1000)：代表二叉树的节点个数。

输入的第二行包括n个整数(其中每个元素a的范围为(1<=a<=1000))：代表二叉树的前序遍历序列。

输入的第三行包括n个整数(其中每个元素a的范围为(1<=a<=1000))：代表二叉树的中序遍历序列。

输出：

对应每个测试案例，输出一行：

如果题目中所给的前序和中序遍历序列能构成一棵二叉树，则输出n个整数，代表二叉树的后序遍历序列，每个元素后面都有空格。

如果题目中所给的前序和中序遍历序列不能构成一棵二叉树，则输出”No”。

样例输入：

81 2 4 7 3 5 6 84 7 2 1 5 3 8 681 2 4 7 3 5 6 84 1 2 7 5 3 8 6

样例输出：

7 4 2 5 8 6 3 1 No

这代码有Bug，只过了一个样例，谁能帮我找出来？

#include <iostream>
#include <string>
#include <cstdio>

using namespace std;
int preorder[1001];
int inorder[1001];
bool isvalid = true;

struct TreeNode{
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int value){val = value; left = NULL; right = NULL;}
};

TreeNode *Construct(int *preorder, int *endpreorder, int *inorder, int *endinorder)
{
	int rootvalue = preorder[0];
	TreeNode *root = new TreeNode(rootvalue);
	if (preorder == endpreorder)
	{
		if ( inorder == endinorder && *preorder == *inorder)
		{
			return root;
		}
		else {
			isvalid = false;
			return NULL;
		}
	}
	int *rootinorder = inorder;
	while(rootinorder <= endinorder  && *rootinorder != rootvalue)
		rootinorder++;
	if (rootinorder > endinorder)
	{
		isvalid = false;
		return NULL;
	}
	int leftlength = rootinorder - inorder;
	int rightlength = endinorder - rootinorder;
	if (leftlength > 0)
	{
		root->left = Construct(preorder + 1, preorder + leftlength, inorder, rootinorder-1);
	}
	if (rightlength > 0)
	{
		root->right  = Construct(preorder+leftlength+1, endpreorder, rootinorder+1, endinorder);
	}
	return root;
}

TreeNode *ConstructTree(int *preorder, int *inorder, int length)
{
	if (preorder == NULL || inorder == NULL || length <= 0)
	{
		return NULL;
	}
	return Construct(preorder, preorder+length-1, inorder, inorder+length-1);
}



void posttraversal(TreeNode *root)
{
	if (root->left)
	{
		posttraversal(root->left);
	}
	if (root->right)
	{
		posttraversal(root->right);
	}
	printf("%d ",root->val);
}

void destroyTree(TreeNode *root)
{
	if(root == NULL)
		return;
	if (root->left)
	{
		destroyTree(root->left);
	}
	if (root->right)
	{
		destroyTree(root->right);
	}
	delete root;
}

int main()
{
	
	int n;
	while(cin>>n)
	{
		for (int i = 0; i < n; i++)
		{
			scanf("%d", &preorder[i]);
		}
		for (int i = 0; i < n; i++)
		{
			scanf("%d", &inorder[i]);
		}
		TreeNode *root = ConstructTree(preorder, inorder, n);
		if (root == NULL || !isvalid)
		{
			printf("No");
		}
		else posttraversal(root);
		printf("\n");
		destroyTree(root);
	}
	//system("pause");
	return 0;
}

【剑指offer】题目1385：重建二叉树,布布扣,bubuko.com

【剑指offer】题目1385：重建二叉树

原文：http://blog.csdn.net/xiaozhuaixifu/article/details/22927897