/
* 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:
vector[HTML_REMOVED] preorder,inorder;
unordered_map[HTML_REMOVED] pos; // 前序遍历的每一个节点在中序遍历中的位置
//构建二叉树, a 表示前序遍历的左端点, b 表示前序遍历的右端点, x 表示中序遍历的左端点 y 表示中序的右端点
TreeNode* build(int a , int b , int x , int y){
if(a > b) return NULL;
TreeNode* root = new TreeNode(preorder[a]);
int k = pos[root->val]; // 表示根节点在中序遍历的位置,用来确定根节点左子树或者右子树的节点个数
int j = k-1-x + (a + 1); // 表示左子树前序遍历的右端点的位置
root->left = build(a+1,j,x,y);
root->right = build(j+1,b,k+1,y);
return root;
}
TreeNode* buildTree(vector<int>& _preorder, vector<int>& _inorder) {
preorder = _preorder;
inorder = _inorder;
int n = preorder.size();// 前序遍历的元素个数
for(int i = 0 ; i < n ; i ++ )
pos[inorder[i]] = i; // 例如pos[9] = 0 表示前序遍历的9在中序遍历的索引为 0 的位置
return build(0,n - 1 , 0 , n - 1);
}
};