construct-binary-tree-from-inorder-and-postorder-traversal

题目描述

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:你可以假设树中没有重复的元素。

题解

和上一题基本一样了，只不过这次从后序数组的后面开始遍历，从中序数组中先构建右子树，再构建左子树。

TreeNode* subTree2(int& index, int left, int right, vector<int>& inorder, vector<int>& postorder)
{
	if (left == right)return NULL;
	if (right - left == 1)
	{
		index--;
		return new TreeNode(inorder[left]);
	}
	TreeNode* root = new TreeNode(postorder[index]);
	int i = left;
	for (; i < right; i++)
	{
		if (inorder[i] == postorder[index])
			break;
	}
	index--; 
	root->right = subTree(index, i + 1, right, inorder, postorder);
	root->left = subTree(index, left, i, inorder, postorder);
	return root;
}
TreeNode * buildTree(vector<int>& inorder, vector<int>& postorder) {
	int vsize = inorder.size();
	if (vsize == 0)return NULL;
	else if (vsize == 1) return new TreeNode(inorder[0]);
	int i = vsize - 1;
	return subTree2(i, 0, vsize, inorder, postorder);
}