输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
限制：
0 <= 节点个数 <= 5000
解:树一般都用递归的方法，这道题解题的关键是找到根节点在前序和中序的位置及关系
/** * 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* buildTree(vector<int>& preorder, vector<int>& inorder) { if(preorder.size()==0||inorder.size()==0) return nullptr; int i_medpos=0; while(i_medpos<inorder.size()) { if(inorder[i_medpos]==preorder[0]) break; i_medpos++; } TreeNode *root=new TreeNode(preorder[0]); //前序数组中去掉根节点,中序数组中根节点的下标，在前序节点中此下标前的都是根节点的左子树 vector<int> left_pre(preorder.begin()+1,preorder.begin()+i_medpos+1); vector<int> right_pre(preorder.begin()+i_medpos+1,preorder.end()); vector<int> left_in(inorder.begin(),inorder.begin()+i_medpos); //中序数组中去掉根节点 vector<int> right_in(inorder.begin()+i_medpos+1,inorder.end()); root->left=buildTree(left_pre,left_in); root->right=buildTree(right_pre,right_in); return root; } };
原文：https://www.cnblogs.com/wangshaowei/p/12318031.html