力扣 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。

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

感觉很复杂，得多做几遍