题意：由前序序列和后序序列构建二叉树（保证树的结点值均不相同），若构建的二叉树唯一，输出Yes和其中序序列；若不唯一，输出No和任意一个二叉树的中序序列。
思路：首先，假定区间下标从0开始，即[0,n-1]。
1.一开始，前序序列的第一个结点和后序序列的最后一个结点相同，且为树的根结点。这一点是确定的。
2.前序序列的第二个值（记为kid）为根结点的孩子节点，但不确定是左孩子还是右孩子。
3.在后序序列中找到kid的位置（下标记为pos），则在后序序列中，位于pos之前的结点均为结点kid的孩子结点（即区间postorder[postL,pos)），记录以kid为根结点的子树的结点个数subTreeCnt=pos-postL+1。
4.1.若在前序序列中，结点kid之后（包括kid本身）的所有结点个数恰为subTreeCnt个（即subTreeCnt==preR-preL），则说明原根结点只有一个孩子结点，即kid，只是无法确定kid是原根结点的左孩子还是右孩子，说明可构建的二叉树不唯一，因为题目无明确要求，在不确定的情况下可统一当做左孩子（或右孩子）处理。
4.2.若在前序序列中，结点kid之后（包括kid本身）的所有结点个数不为subTreeCnt个（其实是大于subTreeCnt个），说明原根结点含有两个孩子结点，则对序列进行递归划分。此时，即——
左子树：preorder[preL+1,preL+subTreeCnt]，postorder[postL,pos]
右子树：preorder[preL+1+subTreeCnt,preR]，postorder[pos+1,postR-1]
注意点：虽然都是递归处理，但是这与【前/后序列+中序序列-->二叉树】的做法还是有细微差别的。本题中，划分的依据不是原根结点本身，而是前序序列的第二个值（即原根结点的某个孩子节点）。
代码：
#include <cstdio> struct Node{ int val; Node *lchild,*rchild; Node(int v):val(v),lchild(NULL),rchild(NULL){} }; int pre[35],post[35]; bool beUnique=true; int n; Node* buildBiTree(int preL,int preR,int postL,int postR) { if(preL>preR) return NULL; if(preL==preR) return new Node(pre[preL]); int rootval=pre[preL], kid=pre[preL+1]; Node* root=new Node(rootval); int pos=postL; while(post[pos]!=kid) pos++; int subTreeCnt=pos-postL+1; if(subTreeCnt==preR-preL){ beUnique=false; root->lchild=buildBiTree(preL+1,preR,postL,pos); root->rchild=NULL; }else{ root->lchild=buildBiTree(preL+1,preL+subTreeCnt,postL,pos); root->rchild=buildBiTree(preL+subTreeCnt+1,preR,pos+1,postR-1); } return root; } void inOrderTraversal(Node* root) { static int cnt=0; if(root){ inOrderTraversal(root->lchild); printf("%d",root->val); cnt++; if(cnt<n) printf(" "); else printf("n");//漏了这句就0分，我服了 inOrderTraversal(root->rchild); } } int main() { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&pre[i]); for(int i=0;i<n;i++) scanf("%d",&post[i]); Node* root=buildBiTree(0,n-1,0,n-1); printf("%sn",beUnique?"Yes":"No"); inOrderTraversal(root); return 0; }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
