题目
思路分析
- 我们可以通过递归实现的二叉树构建函数。它根据给定的先序遍历序列和中序遍历序列构建一棵二叉树，并返回根节点。
- 可以创建一个_build 函数，该函数负责构建二叉树的节点，通过分割先序遍历序列和中序遍历序列，并递归构建左子树和右子树来完成整个二叉树的构建过程。
- 最终，buildTree 函数调用 _build 函数，并返回构建的二叉树的根节点。
代码
class Solution { public: TreeNode* _build(vector<int>& preorder, vector<int>& inorder, int& peri, int begin, int end) { // 如果开始索引大于结束索引，则返回空指针，表示当前子树为空 if (begin > end) { return nullptr; } int rooti = 0; // 在中序遍历序列中找到当前根节点的索引 while (rooti <= end) { if (inorder[rooti] == preorder[peri]) { break; } rooti++; } // 创建当前根节点 TreeNode* root = new TreeNode(preorder[peri++]); // 构建左子树 // 左子树的先序遍历序列为 [begin, rooti-1] // 左子树的中序遍历序列为 [begin, rooti-1] root->left = _build(preorder, inorder, peri, begin, rooti-1); // 构建右子树 // 右子树的先序遍历序列为 [rooti+1, end] // 右子树的中序遍历序列为 [rooti+1, end] root->right = _build(preorder, inorder, peri, rooti+1, end); return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int i = 0; // 调用内部函数 _build 构建二叉树 // 初始时 peri 为 0，表示从先序遍历序列的第一个元素开始构建 // 根据先序遍历序列和中序遍历序列构建二叉树，并返回根节点 TreeNode* root = _build(preorder, inorder, i, 0, preorder.size()-1); return root; } };
代码讲解
首先判断起始索引 begin 是否大于结束索引 end，如果是，则说明当前子树为空，返回空指针。
在中序遍历序列 inorder 中找到当前根节点的索引 rooti，该索引表示根节点在中序遍历中的位置。在循环中，不断遍历中序遍历序列，直到找到与先序遍历序列 preorder[peri] 相等的值。找到后，rooti 就是根节点的索引。
创建当前根节点，节点的值为 preorder[peri]。
根据先序遍历序列和中序遍历序列的特性，可以将当前子树分为左子树和右子树。左子树的先序遍历序列为 preorder[begin, rooti-1]，左子树的中序遍历序列为 inorder[begin, rooti-1]。右子树的先序遍历序列为 preorder[rooti+1, end]，右子树的中序遍历序列为 inorder[rooti+1, end]。
递归调用 _build 函数，分别构建左子树和右子树，并将返回的根节点设置为当前根节点的左孩子和右孩子。
返回当前根节点。
总结：
在 buildTree 函数中，首先定义了一个变量 i，初始值为 0，作为 _build 函数中 peri 的初始值。然后调用 _build 函数，传入先序遍历序列 preorder、中序遍历序列 inorder、i、0 和 preorder.size()-1，即整个序列的起始和结束索引。最后返回构建的二叉树的根节点。
