LeetCode hot100-105从前序与中序遍历序列构造二叉树

class Solution { public: TreeNode* buildTree(vectorint preorder, vectorint inorder) { if(preorder.empty()||inorder.empty()) return nullptr; vectorint lpre,lin,rpre,rin; TreeNode* ansnew TreeNode(preorder[0]);; int flg0; // 分割中序左子树和右子树不含根节点 for(int i0;iinorder.size();i){ if(inorder[i]preorder[0]){ flgi; break; } } for(int i0;iflg;i){ lin.push_back(inorder[i]); } for(int iflg1;iinorder.size();i){ rin.push_back(inorder[i]); } // 分割前序根据左子树的大小 for(int i1;ilin.size();i){ lpre.push_back(preorder[i]); } for(int i 1 lin.size(); i preorder.size(); i) { rpre.push_back(preorder[i]); } ans-leftbuildTree(lpre,lin); ans-rightbuildTree(rpre,rin); return ans; } };class Solution { public: TreeNode* buildTree(vectorint preorder, vectorint 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; } } // 分割中序遍历 vectorint leftInorder(inorder.begin(), inorder.begin() rootIndex); vectorint rightInorder(inorder.begin() rootIndex 1, inorder.end()); // 分割前序遍历 vectorint leftPreorder(preorder.begin() 1, preorder.begin() 1 leftInorder.size()); vectorint 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(vectorint preorder, vectorint inorder) { return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1); } private: TreeNode* build(vectorint preorder, int preStart, int preEnd, vectorint 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; } };