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

题目描述

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

例如，给出

前序遍历 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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

C++

/** * 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
   
    & preorder, vector
    
     & inorder) {
           if(!preorder.size())  return NULL;        return dfs(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);           }     TreeNode* dfs(vector
     
      & preorder, vector
      
       & inorder,int pl, int pr,int il,int ir) {
           if(il>ir)  return NULL;        //找到根在中序遍历中的索引        int index=0;         for(int i=il;i<=ir;i++){
               if(inorder[i]==preorder[pl]){
                   index=i;                break;            }                        }                //建树        TreeNode* root=new TreeNode(preorder[pl]); //根节点        int k=index-il;  //左子树个数        root->left=dfs(preorder,inorder,pl+1,pl+k,il,index-1);        root->right=dfs(preorder,inorder,pl+1+k,pr,1+index,ir);        return root;     }};