[leetcode] 105. Construct Binary Tree from Preorder and Inorder Traversal (Medium)

原题

题意：
根据先序和中序得到二叉树(假设无重复数字)

思路：
先手写一次转换过程，得到思路。
即从先序中遍历每个元素，（创建一个全局索引，指向当前遍历到的元素）在中序中找到该元素作为当前的root，以该节点左边所有元素作为当前root的左支，右同理。
重复分别对左右边所有元素做相同处理。

class Solution
{
public:TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder){int pos = 0;return buildBinary(preorder, inorder, 0, preorder.size(), pos);}private:TreeNode *buildBinary(vector<int> &preorder, vector<int> &inorder, int beg,int end, int &pos){TreeNode *node = NULL;if (beg < end){int i = 0;for (i = beg; i < end; i++){if (preorder[pos] == inorder[i])break;}++pos;node = new TreeNode(inorder[i]);node->left = buildBinary(preorder, inorder, beg, i, pos);node->right = buildBinary(preorder, inorder, i + 1, end, pos);}return node;}
};