学步园

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.

注意没有重复元素很重要，如果有重复元素的话，需要在寻找pos的时候对每个pos都尝试一下

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
    	int psz=preorder.size(),isz=inorder.size();
		assert(psz==isz);
		return create(preorder,0,psz-1,inorder,0,isz-1);
    }
	TreeNode* create(vector<int>& pre,int pl,int pr,vector<int>& in,int il,int ir)
	{
		if ( pl>pr )
		{
			assert(il>ir);
			return NULL;
		}
		int val=pre[pl];
		int pos=il;
		for(;pos<=ir;pos++)
			if ( in[pos]==val)
				break;
		assert(pos<=ir);
		TreeNode* root=new TreeNode(val);
		int ln=pos-il;
		int rn=ir-pos;
		root->left=create(pre,pl+1,pl+ln,in,il,pos-1);
		root->right=create(pre,pl+ln+1,pr,in,pos+1,ir);
		return root;
	}
};