学步园

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

Note:

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

很经典的老题了，相信解法大家都会，就不说了。

代码如下，注意我添加了很多断言来判断给定的数据是否正确，在做OJ的时候可以不需要，但是如果在面试的时候写上这些错误判断是很加分的项哦

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 #define vi vector<int>
#define tn TreeNode 
class Solution {
public:
    tn* buildTree(vi& pre,vi& in)
{
    int np=pre.size(),ni=in.size();
	assert(np==ni);
	if(np==0)
		return NULL;
	return construct(pre,0,np-1,in,0,ni-1);
}

tn* construct(vi& pre,int pl,int pr,vi& in,int il,int ir)
{
	assert(pr-pl==ir-il);
	if(pl>pr)
		return NULL;
	tn* root=new tn(pre[pl]);
	int k=il;
	for(;k<=ir;k++)
	{
		if(pre[pl]==in[k])
			break;
	}
    assert(k<=ir);

	root->left=construct(pre,pl+1,pl+(k-il),in,il,k-1);
	root->right=construct(pre,pl+(k-il)+1,pr,in,k+1,ir);
	return root;
}


};