本文共 1148 字，大约阅读时间需要 3 分钟。

1. 题目

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7]返回如下的二叉树：    3   / \  9  20    /  \   15   7 限制：0 <= 节点个数 <= 5000

来源：力扣（LeetCode）

2. 解题

相关题目：

请参考上面链接文章，不再赘述。

class Solution {
   	unordered_map
   
     in;public:    TreeNode* buildTree(vector
    
     & preorder, vector
     
      & 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(vector
      
       & preorder, int sp, int ep, vector
       
        & inorder, int si, int ei)    {
       	if(ep-sp<0)    		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,sp+1,sp+leftlen,inorder,si,Proot-1);    	root->right = build(preorder,sp+leftlen+1,sp+leftlen+rightLen,inorder,Proot+1,ei);    	return root;    }};
       
      
     
    
   

转载地址：https://michael.blog.csdn.net/article/details/104294946 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！