题目描述题目要求根据二叉树的先序遍历preorder\texttt{preorder}preorder和中序遍历inorder\texttt{inorder}inorder字符串恢复二叉树并输出后序遍历postorder\texttt{postorder}postorder字符串。树中每个节点用大写字母表示且所有字母唯一。输入格式输入包含多个测试用例每行两个字符串分别表示先序和中序遍历序列。输入以文件结束符EOF\texttt{EOF}EOF终止。输出格式对于每个测试用例输出一行后序遍历序列。样例输入DBACEGF ABCDEFG BCAD CBAD输出ACBFGED CDAB题目分析本题的核心是根据先序和中序重构二叉树然后输出后序。重构方法先序遍历的第一个字符为根节点。在中序遍历中找到根节点的位置左侧为左子树的中序遍历右侧为右子树的中序遍历。根据左子树的节点数在先序遍历中划分出左子树的先序遍历和右子树的先序遍历。递归处理左右子树。后序遍历输出顺序为左子树后序、右子树后序、根。递归实现直接递归输出后序无需显式构建树。函数postorder(preorder, inorder)\texttt{postorder(preorder, inorder)}postorder(preorder, inorder)若字符串为空返回。根 preorder[0]\textit{preorder}[0]preorder[0]。在inorder\textit{inorder}inorder中找到根的位置ppp。递归左子树postorder(preorder.substr(1, p), inorder.substr(0, p))\textit{postorder(preorder.substr(1, p), inorder.substr(0, p))}postorder(preorder.substr(1, p), inorder.substr(0, p))。递归右子树postorder(preorder.substr(p1), inorder.substr(p1))\textit{postorder(preorder.substr(p1), inorder.substr(p1))}postorder(preorder.substr(p1), inorder.substr(p1))。输出根。复杂度分析每个节点处理一次时间复杂度O(n2)O(n^2)O(n2)查找根位置n≤26n \le 26n≤26可接受。代码实现// Tree Recovery// UVa ID: 536// Verdict: Accepted// Submission Date: 2016-08-14// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;voidpostorder(string preorder,string inorder){if(preorder.length()0)return;// 找到根结点。introot0;for(;rootinorder.length();root)if(inorder[root]preorder.front())break;// 在左子树中递归。postorder(preorder.substr(1,root),inorder.substr(0,root));// 在右子树中递归。postorder(preorder.substr(root1),inorder.substr(root1));// 输出根。coutpreorder.front();}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string order1,order2;while(cinorder1order2){postorder(order1,order2);cout\n;}return0;}
