AcWing 18. 重建二叉树（C++）- dfs+有价值

缺乏、安全感 2022-08-28 12:00 110阅读 0赞

题目链接：[https://www.acwing.com/problem/content/description/23/][https_www.acwing.com_problem_content_description_23]  
题目如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]  
思路：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

/**
     * 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:
        vector<int> pre,in;//为了方便，用作全局变量，因为递归中也要使用两个vector
        map<int,int> hash;//用来记录中序遍历中每个数的位置
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        
            pre=preorder,in=inorder;
            
            for(int i=0;i<in.size();i++)
                hash[in[i]]=i;
                
            return dfs(0,pre.size()-1,/**/0,in.size()-1);//前两个值为preorder中下标的位置，后两个值为inorder中下标的位置
        }
        
        TreeNode* dfs(int pre_left,int pre_right,/**/int in_left,int in_right){
        
            if(pre_left>pre_right) return NULL;//当前区间为0，返回nullptr
            
            TreeNode* root=new TreeNode(pre[pre_left]);//先序遍历的第一个元素为“树根”节点
            int pos=hash[root->val];//得到当前树根在中序遍历中的下标，且左半部分为左子树，右半部分为右子树
            
            root->left=dfs(pre_left+1,(pre_left+1)+(pos-in_left)-1,/**/in_left,pos-1);
            root->right=dfs((pre_left+1)+(pos-in_left)-1+1,pre_right,/**/pos+1,in_right);
            
            return root;
        }
    };

[https_www.acwing.com_problem_content_description_23]: https://www.acwing.com/problem/content/description/23/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/1908682160134182ba1b3d2c5420b59e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/c38cfe0fd97a4471b6b74ba25f61844e.png