105. Construct Binary Tree from Preorder and Inorder Traversal

经典题目，同理还有通过inorder和postorder构建binary tree
Given preorder and inorder traversal of a tree, construct the binary tree.

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

同样树的问题采用递归解决

对于任意一颗树而言，前序遍历的形式总是

[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是

[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

一个关键点在于前序中，关于左子树的范围判定，注意到与inorder中的左子树nodes数一样多，即可轻松破解。

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* myBuild(vector<int> preorder, vector<int> inorder, int preL, int preR, int inL, int inR){if(preL > preR || inL > inR){return nullptr;}TreeNode* root = new TreeNode(preorder[preL]);int inorderRoot;for(int i = inL; i <= inR; i++){if(inorder[i] == preorder[preL]){inorderRoot = i;break;}}TreeNode* lChild = myBuild(preorder, inorder, preL + 1, inorderRoot - inL + preL, inL, inorderRoot - 1);TreeNode* rChild = myBuild(preorder, inorder, inorderRoot - inL + preL + 1, preR, inorderRoot + 1, inR);root->left = lChild;root->right = rChild;return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {return myBuild(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);}
};

另外关于inorder中root的查找，可以事先通过全局unordered_map存储元素与index的关系。更快