力扣 hot100 Day49

105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

//抄的
class Solution {
private:
    unordered_map<int, int> index;

    TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, 
                          int pre_left, int pre_right, 
                          int in_left, int in_right) {
        if (pre_left > pre_right) return nullptr;

        int root_val = preorder[pre_left];
        TreeNode* root = new TreeNode(root_val);

        int in_root = index[root_val];
        int left_size = in_root - in_left;

        root->left = myBuildTree(preorder, inorder, 
                                pre_left + 1, pre_left + left_size, 
                                in_left, in_root - 1);
        root->right = myBuildTree(preorder, inorder, 
                                 pre_left + left_size + 1, pre_right, 
                                 in_root + 1, in_right);
        return root;
    }

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.size() != inorder.size() || preorder.empty()) return nullptr;

        for (int i = 0; i < inorder.size(); ++i) {
            index[inorder[i]] = i;
        }

        return myBuildTree(preorder, inorder, 
                          0, preorder.size() - 1, 
                          0, inorder.size() - 1);
    }
};

基本逻辑如下

1. ​​从 preorder 获取当前根节点​​（即 preorder[0]）。
2. ​​在 inorder 中找到根节点的位置 root_idx​​：
   • inorder[root_idx] 是根节点。
   • inorder[0 ... root_idx-1] 是左子树的中序遍历。
   • inorder[root_idx+1 ... end] 是右子树的中序遍历。
3. ​​递归构建左子树和右子树​​：
   • ​​左子树的 preorder​​：preorder[1 ... left_size]（left_size 是左子树的节点数）。
   • ​​右子树的 preorder​​：preorder[left_size+1 ... end]。
4. ​​终止条件​​：如果 preorder 或 inorder 为空，返回 nullptr。

总体是分治思想，一步步构建二叉树，引入哈希表用于快速查找根节点位置

感觉很复杂，得多做几遍