题解 | 重建二叉树

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <unordered_map>
class Solution {
public:
    unordered_map<int, int> vin;  //以节点值为键，在数组的下标为值；

    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        int n = preOrder.size();
        for(int i = 0; i<n; ++i){
            vin[vinOrder[i]] = i;
        }
        
        return solu(0, n-1, 0, n-1, preOrder, vinOrder); 
    }

    TreeNode* solu(int pre_start, int pre_end, int vin_start, int vin_end,  vector<int>& preOrder, vector<int>& vinOrder){ 
        //每次递归都是一层前序遍历：根节点-》左子树-》右子树，可以确定根节点
        //前中序遍历可以确定左子树和右子树的节点的个数，从而确定下一层在preOrder中的范围和位置，进入下一层递归；
        if(pre_start > pre_end)return nullptr;

        auto* root_curr = new TreeNode(preOrder[pre_start]); //创建当前根节点；

        int root_vin_index = vin[preOrder[pre_start]]; //找到根节点在中序遍历的下标；
        int left_nums = root_vin_index - vin_start;  //计算当前根节点的左子树有多少节点;
        int right_nums = vin_end - root_vin_index; //当前根节点的右子树有多少节点；
        
        root_curr->left = solu(pre_start+1, pre_start+left_nums, vin_start, root_vin_index-1 ,preOrder, vinOrder); 

        root_curr->right = solu(pre_start+left_nums+1, pre_end , root_vin_index+1 , vin_end , preOrder , vinOrder);

        return root_curr;
    }
};