输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 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
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/391326
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
