免费1级做看网站,制作单页网站要网址,微信用大型网站站做跳板,东莞外贸网站推广建设1. 题目
输入某二叉树的前序遍历和中序遍历的结果#xff0c;请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如#xff0c;给出前序遍历 preorder [3,9,20,15,7]
中序遍历 inorder [9,3,15,20,7]
返回如下的二叉树#xff1a;3/ \9 20/ …1. 题目
输入某二叉树的前序遍历和中序遍历的结果请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如给出前序遍历 preorder [3,9,20,15,7]
中序遍历 inorder [9,3,15,20,7]
返回如下的二叉树3/ \9 20/ \15 7限制
0 节点个数 5000来源力扣LeetCode 链接https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
相关题目 LeetCode 105. 已知前序中序 求二叉树 LeetCode 106. 已知中序后序 求二叉树 LeetCode 1008. 先序遍历构造二叉树已知先序求二叉搜索树 POJ 2255 Tree Recovery已知前序中序求后序 POJ 1577 Falling Leaves二叉查找树
请参考上面链接文章不再赘述。
class Solution {unordered_mapint,int in;
public:TreeNode* buildTree(vectorint preorder, vectorint inorder) {if(preorder.empty())return NULL;int i, n preorder.size();for(i 0; i n; i)in[inorder[i]] i;return build(preorder,0,n-1,inorder,0,n-1);}TreeNode* build(vectorint preorder, int sp, int ep, vectorint inorder, int si, int ei){if(ep-sp0)return NULL;TreeNode* root new TreeNode(preorder[sp]);int Proot in[preorder[sp]];int leftlen Proot-si;int rightLen ei-Proot;root-left build(preorder,sp1,spleftlen,inorder,si,Proot-1);root-right build(preorder,spleftlen1,spleftlenrightLen,inorder,Proot1,ei);return root;}
};
