首页 > 代码库 > PAT甲题题解-1119. Pre- and Post-order Traversals (30)-(根据前序、后序求中序)
PAT甲题题解-1119. Pre- and Post-order Traversals (30)-(根据前序、后序求中序)
(先说一句,题目还不错,很值得动手思考并且去实现。)
题意:根据前序遍历和后序遍历建树,输出中序遍历序列,序列可能不唯一,输出其中一个即可。
已知前序遍历和后序遍历序列,是无法确定一棵二叉树的,原因在于如果只有一棵子树可能是左孩子也有可能是右孩子。由于只要输出其中一个方案,所以假定为左孩子即可。下面就是如何根据前序和后序划分出根节点和左右孩子,这里需要定义前序和后序的区间范围,分别为[preL,preR],[postL,postR]。
一开始区间都为[1,n],可以发现前序的第一个和后序的最后一个为根节点root,前序的第二个值val为其某子树的根节点(但还无法确定是左孩子or右孩子)。在后序中找对应的值所在的位置postIdx,则postIdx之前的节点均为val的孩子节点,统计其个数num。那么我们就可以划分区间:
若num个数=preR-preL-1,即val后面的个数都是其子节点,那么二叉树不唯一,将其作为root的左子树处理。
否则划分为左子树区间和右子树对应的前序和后序区间,顺便更新下root的左孩子preL+1,右孩子preL+num+2:
preOrder:[preL+1,preL+num+1],postOrder:[postL,postIdx];
preOrder:[preL+num+2,preR],postOrder:[postIdx+1,postR-1];
然后递归划分即可
拿样例举例:
1 (2) [3 {4 6 7} <5>]
(2) [{6 7 4} <5> 3] 1
不同的括号对应不同的子树区间
第一次递归划分了(2)-(2),[3 4 6 7 5]-[6 7 4 5 3]
由于(2)只有一棵,不继续划分。
第二次递归划分了{4 6 7}-{6 7 4},<5>-<5>
第三次递归划分了(6)-(6),(7)-(7)
结束
#include <iostream> #include <cstdio> #include <algorithm> #include <string.h> using namespace std; const int maxn=35; int preOrder[maxn]; int postOrder[maxn]; bool isUnique=true; struct Node{ int left=-1,right=-1; }node[maxn]; /* [preL,preR] is current sequence interval of pre-order [postL,postR] is current sequence interval of post-order */ void build(int preL,int preR,int postL,int postR){ if(preL>=preR){ return; } int fa=preL; //前序遍历的第一个为根节点,第二个为子树的根节点,可能是左孩子也可能是右孩子 int val=preOrder[preL+1]; int postIdx; for(int i=postL;i<postR;i++){ if(val==postOrder[i]){ postIdx=i; //val在后序遍历中的索引 break; } } int num=postIdx-postL; //以val为根节点的子树节点个数 //即以val为根节点的子树只有一棵孩子,那么既可以为左孩子也可以为右孩子,所以不唯一 if(preR-preL-1==num){ isUnique=false; } node[fa].left=preL+1; //不唯一的话,看做左孩子 build(preL+1,preL+num+1,postL,postIdx); //如果以preL+1为根节点的子树的节点个数小于fa的所有子树节点的个数,说明fa还有右孩子 if(preR-preL-1>num){ node[fa].right=preL+num+2; build(preL+num+2,preR,postIdx+1,postR-1); } } bool first=true; void inOrder(int root){ if(root==-1){ return; } inOrder(node[root].left); if(first){ first=false; printf("%d",preOrder[root]); } else printf(" %d",preOrder[root]); inOrder(node[root].right); } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&preOrder[i]); for(int i=1;i<=n;i++) scanf("%d",&postOrder[i]); build(1,n,1,n); if(isUnique) printf("Yes\n"); else printf("No\n"); inOrder(1); printf("\n"); //否则格式错误 return 0; }
PAT甲题题解-1119. Pre- and Post-order Traversals (30)-(根据前序、后序求中序)