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

1.题目

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:

2.思路分析

• 方法：递归
• 为什么用unordered_map？因为采用这个可以很快的找到中序遍历数字对应的下标
• 为什么要算出size？因为你是下标操作，所以每次递归构造的时候，需要给出左右子树的范围
• 构造根节点，然后递归的构造左子树，连接到根节点，右子树同理
• 注意：①执行函数时，需要进行判空操作
• ② 一定要返回，将所有的节点连接起来
• ③ mybuildTree函数的后四个参数都是下标

3. 代码展示

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */

class Solution {
   public:   unordered_map
   
     index;   TreeNode* mybuildTree(vector
    
     & preorder, vector
     
      & inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right)   {
          if(preorder_left > preorder_right)           return nullptr;       int preorder_root = preorder_left;       int inorder_root = index[preorder[preorder_left]];       int size = inorder_root - inorder_left;       TreeNode* root = new TreeNode(inorder[inorder_root]);       root->left = mybuildTree(preorder, inorder, preorder_left + 1, preorder_left + size, inorder_left, inorder_left + size);//inorder_root - 1);       root->right = mybuildTree(preorder, inorder, preorder_left + size + 1, preorder_right, inorder_root + 1, inorder_right);       return root;   }   TreeNode* buildTree(vector
      
       & preorder, vector
       
        & inorder) {
          int n = inorder.size();       for(int i = 0; i < inorder.size(); ++i){
              index[inorder[i]] = i;       }       return mybuildTree(preorder, inorder, 0, n - 1, 0, n - 1);   }};
       
      
     
    
   

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