二叉树测试用例：

preOrder: ABDGCEFH
inOrder: DGBAECHF
postOrder: GDBEHFCA

1. 已知二叉树前序遍历序列和中序遍历序列可以确定一颗二叉树。
2. 已知二叉树中序遍历序列和后序遍历序列可以确定一颗二叉树。
3. 已知二叉树前序遍历序列和后序遍历序列不能确定一颗二叉树。

已知二叉树前序和中序遍历序列，构造二叉树，C++实现：

#include<iostream>
#include<stack>
#include<cstring>
using namespace std;

//二叉树结点定义
struct node {
	char value;
	node *lchild;
	node *rchild;
	node(char ch) {
		value = ch;
		lchild = NULL;
		rchild = NULL;
	}
};

//递归 二叉树前序遍历
void preOrder(node *root)
{
	if (root)
	{
		cout << root->value;
		preOrder(root->lchild);
		preOrder(root->rchild);
	}
}

//递归 二叉树中序遍历
void inOrder(node *root)
{
	if (root)
	{
		inOrder(root->lchild);
		cout << root->value;
		inOrder(root->rchild);
	}
}

//递归 二叉树后序遍历
void postOrder(node *root)
{
	if (root)
	{
		postOrder(root->lchild);
		postOrder(root->rchild);
		cout << root->value;
	}
}

node *buildBitree(string pre, string in)
{
	int len = pre.length();
	if (len <= 0)
	{
		return NULL;
	}
	node *root = new node(pre[0]);
	int n = in.find(pre[0]);
	root->lchild = buildBitree(pre.substr(1, n), in.substr(0, n));
	root->rchild = buildBitree(pre.substr(n + 1, len - n - 1), in.substr(n + 1, len - n - 1));
	return root;
}

int main()
{
	char pre[100], in[100];
	while (cin >> pre >> in)
	{
		node *root = buildBitree(pre, in);
		postOrder(root);
		cout << endl;
		//inOrder(root);
		//cout << endl;
		//preOrder(root);
		//cout << endl;
	}
	return 0;
}

已知二叉树中序和后序遍历序列，构造二叉树，C++实现：

node *buildBitree(string post, string in)
{
	int len = post.length();
	if (len <= 0)
	{
		return NULL;
	}
	node *root = new node(post[len - 1]);
	int n = in.find(post[len - 1]);
	root->lchild = buildBitree(post.substr(0, n), in.substr(0, n));
	root->rchild = buildBitree(post.substr(n, len - n - 1), in.substr(n + 1, len - n - 1));
	return root;
}

Notes:

  str.length()、str.size()均用来求取字符串的长度。