2 条题解
-
0
递归求解的 注释过程,用于讲解:
#include <bits/stdc++.h> using namespace std; string buildpostorder(string pres,string ins){ // 如果先序 或中序 有一个为空, 说明没有子树 // 取得先序字符串的第一个字符- 根节点 //在中序字符串里面查找根节点的位置 //在中序字符串里面取得 中序的左子树 和右子树 string inleft= string inright= //计算左子树 的 长度 int leftlen= ; //从先序串中 截取 左右子树的 先序序列 //跳过先序字符串的根节点 取leftlen长度 string preleft = substr(); //截图右子树的先序串 inright在先序串中的 串 string preright = //递归构造左子树的后续 和右子树的后续 string postleft =buildpostorder(); string posright =buildpostorder(); return postleft+posright+根节点 ; } int main(){ string prestring ,instring; cin>> ; string poststring = buildpostorder(); cout<< return 0; } -
0
递归求解方法:
#include <bits/stdc++.h> using namespace std; string buildPostOrder(const string &pre, const string &in) { // 如果先序或中序为空,说明没有子树 if (pre.empty() || in.empty()) return ""; // 根节点为先序遍历的第一个字符 char root = pre[0]; // 在中序序列中找到根节点的位置 int rootPos = (int)in.find(root); // 中序遍历中,rootPos左侧为左子树中序,右侧为右子树中序 string inLeft = in.substr(0, rootPos); string inRight = in.substr(rootPos + 1); // 左子树长度 int leftLen = (int)inLeft.size(); // 从先序中截取左、右子树的先序序列 // 跳过根节点 pre[0],接下来 leftLen 个字符属于左子树先序 string preLeft = pre.substr(1, leftLen); // 剩下的属于右子树先序 string preRight = pre.substr(1 + leftLen); // 递归构造左子树的后序和右子树的后序 string postLeft = buildPostOrder(preLeft, inLeft); string postRight = buildPostOrder(preRight, inRight); // 后序遍历 = 左子树后序 + 右子树后序 + 根节点 return postLeft + postRight + root; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); string preorder, inorder; cin >> preorder >> inorder; string postorder = buildPostOrder(preorder, inorder); cout << postorder << "\n"; return 0; }
- 1
信息
- ID
- 817
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 26
- 已通过
- 14
- 上传者