leetcode Construct Binary Tree from Preorder and Inorder Traversal

Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

和construct binary tree from inorder and postorder traversal 的构造方法是一样的。

http://blog.csdn.net/kenden23/article/details/15500733

这次是使用preorder数组定位跟节点，利用inorder数组分左右子树。

关键点：

1 定位每层的根节点

2 计算好offset

//2014-2-16 update
	TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) 
	{
		return build(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
	}
	TreeNode *build(vector<int> &preorder, int pre1, int pre2,
		vector<int> &inorder, int in1, int in2)
	{
		if (pre1 > pre2) return nullptr;
		TreeNode *root = new TreeNode(preorder[pre1]);
		int offset = 0;
		for ( ; inorder[in1+offset] != preorder[pre1]; offset++);

		root->left = build(preorder, pre1+1, pre1+offset, inorder, in1, in1+offset-1);
		root->right = build(preorder, pre1+offset+1, pre2, inorder, in1+offset+1, in2);
		return root;
	}