题目
思路
代码
class Solution { public: TreeNode* _build(vector<int>& inorder, vector<int>& postorder,int & peri,int lefti,int righti) { if(lefti>righti) { return nullptr; } int rooti=0; while(rooti<=righti) { if(postorder[peri]==inorder[rooti]) { break; } rooti++; } //[lefti,rooti-1][rooti][rooti+1,righti] TreeNode * root=new TreeNode(postorder[peri--]); root->right=_build(inorder,postorder,peri,rooti+1,righti); root->left=_build(inorder,postorder,peri,lefti,rooti-1); return root; } TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { int i=postorder.size()-1; TreeNode *root=_build(inorder,postorder,i,0,postorder.size()-1); return root; } };
代码讲解
_build 函数是一个递归函数，用于构建二叉树的子树。它接收中序遍历序列 inorder、后序遍历序列 postorder、一个引用 peri、当前子树的左边界 lefti 和右边界 righti 作为参数。
首先，检查左边界 lefti 是否大于右边界 righti，如果是，说明当前子树为空，返回 nullptr。
在后序遍历序列中，找到当前根节点的值 postorder[peri] 在中序遍历序列中的位置 rooti。
创建一个新的节点 root，值为 postorder[peri–]，即后序遍历序列的最后一个元素。
递归地调用 _build 函数构建右子树，传入中序遍历序列 inorder、后序遍历序列 postorder、引用 peri、rooti+1 和 righti 作为参数。
递归地调用 _build 函数构建左子树，传入中序遍历序列 inorder、后序遍历序列 postorder、引用 peri、lefti 和 rooti-1 作为参数。
返回根节点 root。
buildTree 函数是主函数，用于调用 _build 函数构建整棵二叉树。它接收中序遍历序列 inorder 和后序遍历序列 postorder 作为参数。
初始化变量 i 为 postorder 的最后一个索引，即后序遍历序列的最后一个元素。
调用 _build 函数构建二叉树的根节点，传入中序遍历序列 inorder、后序遍历序列 postorder、引用 i、0 和 postorder.size()-1 作为参数。
返回构建的二叉树的根节点 root。
（本题完）
