重建二叉樹LeetCode

給出一棵樹的先序周遊和中序周遊，重建出整棵樹。

思路

先序周遊的第一個值是根節點，在中序周遊序列裡根節點左邊是左子樹，右邊是右子樹。中序周遊裡得到左子樹的長度在先序周遊裡确定左子樹，這樣又得到了左子樹的先序周遊和中序周遊，以此類推得到遞歸樹。

map<int,int> Save;///後續清單的元素索引，根據元素可以很快得到索引。
TreeNode*Build(vector<int>&preorder,int Leftstart,int Leftend,
vector<int> &inorder,int Rightstart,int Rightend,map<int,int>&Save)
{
	if(Leftstart>Leftend)
	{
		return null;
	}
	int val = preorder[Leftstart];
	TreeNode*root = new TreeNode(val);
	if(Leftstar==Leftend)
	{
		return root;
	}
	else
	{
		int middle = Save[val];
		int leftLength= middle - Rightstart;
		int rightLength = Rightend - middle;
		TreeNode *left = Build(preorder,Leftstart+1,LeftLength+Leftstart,inorder,rightstart,middle-1,map);
		TreeNode *right = Build(preorder,Leftend-rightLength+1,Leftend,inorder,middle+1,Rightend,map);
		root->left = left;
		root->right = right;
		return root;
	}
}