还不快抢沙发

添加新评论

根据一棵树的中序遍历与后序遍历构造二叉树。 例如,给出 ``` 中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] ``` 返回如下的二叉树: ``` 3 / \ 9 20 / \ 15 7 ``` 解题思路:后序遍历最后一个元素为根节点m,右侧元素个数为n,右节点为m-1,左节点为m-1-n。 ``` typedef vector::iterator Iter; TreeNode *buildTreeRecur(Iter istart, Iter iend, Iter pstart, Iter pend) { if (istart == iend) return NULL; int val = *pstart; Iter iter = find(istart, iend, val); TreeNode* root = new TreeNode(val); size_t length = distance(iter, iend) - 1; root->left = buildTreeRecur(istart, iter, pstart + 1 + length, pend); root->right = buildTreeRecur(iter + 1, iend, pstart + 1, pend); return root; } TreeNode *buildTree(vector &inorder, vector &postorder) { reverse(postorder.begin(), postorder.end()); return buildTreeRecur(inorder.begin(), inorder.end(), postorder.begin(), postorder.end()); } ```