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。

總體是分治思想，一步步構建二叉樹，引入哈希表用于快速查找根節點位置

感覺很復雜，得多做幾遍