class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { if(preorder.empty()||inorder.empty()) return nullptr; vector<int> lpre,lin,rpre,rin; TreeNode* ans=new TreeNode(preorder[0]);; int flg=0; // 分割中序：左子树和右子树（不含根节点） for(int i=0;i<inorder.size();++i){ if(inorder[i]==preorder[0]){ flg=i; break; } } for(int i=0;i<flg;++i){ lin.push_back(inorder[i]); } for(int i=flg+1;i<inorder.size();++i){ rin.push_back(inorder[i]); } // 分割前序：根据左子树的大小 for(int i=1;i<=lin.size();++i){ lpre.push_back(preorder[i]); } for(int i = 1 + lin.size(); i < preorder.size(); ++i) { rpre.push_back(preorder[i]); } ans->left=buildTree(lpre,lin); ans->right=buildTree(rpre,rin); return ans; } };
![]()
class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { if (preorder.empty() || inorder.empty()) return nullptr; // 根节点是前序遍历的第一个元素 int rootVal = preorder[0]; TreeNode* root = new TreeNode(rootVal); // 在中序遍历中找到根节点位置 int rootIndex = 0; for (int i = 0; i < inorder.size(); ++i) { if (inorder[i] == rootVal) { rootIndex = i; break; } } // 分割中序遍历 vector<int> leftInorder(inorder.begin(), inorder.begin() + rootIndex); vector<int> rightInorder(inorder.begin() + rootIndex + 1, inorder.end()); // 分割前序遍历 vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + 1 + leftInorder.size()); vector<int> rightPreorder(preorder.begin() + 1 + leftInorder.size(), preorder.end()); // 递归构建左右子树 root->left = buildTree(leftPreorder, leftInorder); root->right = buildTree(rightPreorder, rightInorder); return root; } };
![]()
class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1); } private: TreeNode* build(vector<int>& preorder, int preStart, int preEnd, vector<int>& inorder, int inStart, int inEnd) { if (preStart > preEnd || inStart > inEnd) return nullptr; TreeNode* root = new TreeNode(preorder[preStart]); // 在中序中找到根节点 int rootIndex = inStart; while (inorder[rootIndex] != preorder[preStart]) rootIndex++; int leftSize = rootIndex - inStart; // 递归构建 root->left = build(preorder, preStart + 1, preStart + leftSize, inorder, inStart, rootIndex - 1); root->right = build(preorder, preStart + leftSize + 1, preEnd, inorder, rootIndex + 1, inEnd); return root; } };
![]()
