PAT (Advanced Level) Practice 1119 Pre- and Post-order Traversals (30 分) 凌宸1642

题目描述：

Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences, or preorder and inorder traversal sequences. However, if only the postorder and preorder traversal sequences are given, the corresponding tree may no longer be unique.

Now given a pair of postorder and preorder traversal sequences, you are supposed to output the corresponding inorder traversal sequence of the tree. If the tree is not unique, simply output any one of them.

译：保证一颗二叉树中的所有结点的值都是不同的正整数。给定一对后序序列和中序序列，或者前序序列和中序序列可以唯一的确定一颗二叉树。但是，如果只给定后序序列和前序序列，相应的树就可能不再唯一。

现在给定一对后序序列和前序序列，你应该输出相应的二叉树的中序序列。如果这棵树不唯一，简单的输出其中的一个中序序列即可。

Input Specification (输入说明):

Each input file contains one test case. For each case, the first line gives a positive integer N (≤ 30), the total number of nodes in the binary tree. The second line gives the preorder sequence and the third line gives the postorder sequence. All the numbers in a line are separated by a space.

译：每个输入文件包含一个测试用例。 对于每种情况，第一行给出一个整数 N (≤ 30），表示一颗二叉树的结点总数。第二行给出前序序列，第三行给出后序序列。所有在一行中的数字之间用一个空格隔开。

output Specification (输出说明):

For each test case, first printf in a line Yes if the tree is unique, or No if not. Then print in the next line the inorder traversal sequence of the corresponding binary tree. If the solution is not unique, any answer would do. It is guaranteed that at least one solution exists. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

译：对于每种情况，首先第一行，如果这棵树是唯一的，则打印 Yes ，否则打印 No 。然后再第二行打印对应数的中序序列。如果解不唯一，任何一个中序序列都满足要求。题目保证至少存在一个解。所有的数字必须用一个空格隔开，并且行末没有多余的空格。

Sample Input1 (样例输入1):

7
1 2 3 4 6 7 5
2 6 7 4 5 3 1

Sample Output1 (样例输出1):

Yes
2 1 6 4 7 3 5

Sample Input2 (样例输入2):

4
1 2 3 4
2 4 3 1

Sample Output2 (样例输出2):

No
2 1 3 4

The Idea：

• 首先得理解 为什么 前序 + 后序 重建得到的二叉树是不唯一的！
  • 存在这种不唯一性的原因在于：一个结点只有一个孩子结点之时的情况！
  • 不妨假设 A 结点只有一个孩子结点 B ，则先序遍历一定是 A B , 而后序序列一定是 B A ，这里没有涉及 B 究竟是 A的左孩子还是右孩子，但结果不会受影响。这也就是不唯一性的原因所在。
• 熟悉 前序 + 中序 重建二叉树 和 后序 + 中序 重建二叉树 的过程。
• 借鉴，上述两种方法，以及不唯一性的原因，构造先序 + 后序 重建二叉树的方法。
• 我们不妨假设，只有一个孩子结点时，这个孩子结点为 右孩子 ，这样方便我们求解。
• 考虑到我们只需要求解中序序列，以及是否唯一，唯一可以利用一个bool型遍量标记。而中序序列，可以模拟建树过程中就能得到，所以有了如下不建树的解法。
  • 使用 4 个 遍历记录左右子树的边界：preL , preR , postL , postR
  • 正常情况下，先序序列的第一个 pre[preL] 以及后序遍历的最后一个 post[postR] ，都是根节点。
    • 然后我们找到，先序序列 pre 中，与后序序列根节点前一个元素 post[postR -1]相等的位置 index，正常情况下，此时这个结点左边的就是左子树, 即pre[preL + 1] ~ pre[index - 1]和 post[postL] ~ post[postL + (index - preL - 1) - 1]，右边的就是右子树 ，即pre[index] ~ pre[preR]和 post[postL + (index - preL - 1)] ~ post[postR - 1]。如果发现此时左子树的节点数为 0 ，则表示这个结点只有一个孩子结点，则结果就不唯一了。递归访问/模拟重建左子树。
  • 访问此时的根节点，将根节点的值压入栈中。
  • 递归访问/模拟重建右子树。

The Codes - do not build the Tree :

#include<bits/stdc++.h>
using namespace std ;
vector<int> pre , post , in ;
int n ;
bool isUnique = true ;
void getInorder(int preL , int preR , int postL , int postR){
	if(preL == preR){
		in.push_back(pre[preL]) ;
		return ; 
	}
	if(pre[preL] == post[postR]){
		int idx = preL + 1 , numLeft ;
		for(; idx <= preR ; idx ++)  // 找到根节点的前一个节点在前序序列中的位置 
			if(pre[idx] == post[postR - 1]) 
				break ;
		numLeft = idx - preL - 1 ;
		if(idx - preL > 1){ // 左子树非空 ，则递归访问其左子树，
			getInorder(preL + 1 , idx - 1 , postL , postL + numLeft - 1 ) ;
		}else  isUnique = false ; // 左子树为空，则默认在右子树，且此时不唯一
		in.push_back(post[postR]) ; // 访问根节点
		getInorder(idx , preR , postL + numLeft , postR - 1 ) ;//访问右子树
	}
}
int main(){
	scanf("%d" , &n) ;
	pre.resize(n) ;
	post.resize(n) ;
	for(int i = 0 ; i < n ; i ++)scanf("%d" , &pre[i]) ;
	for(int i = 0 ; i < n ; i ++)scanf("%d" , &post[i]) ;
	getInorder(0 , n - 1 , 0 , n - 1) ;
	printf("%s\n%d", isUnique == true ? "Yes" : "No", in[0]);
	for (int i = 1; i < in.size(); i++)
		printf(" %d", in[i]);
	printf("\n");
	return 0 ;
}

The Idea Plus :

• 经过上面的分析，我们知道，先序 + 后序重建二叉树，得到的二叉树是不唯一的。由此引发了我的思考。

  • 先序 + 后序重建二叉树，可以得到唯一的 层序序列 ！
  • 先序 + 后序重建二叉树，可以得到具体会产生多少种不同的二叉树！

• 对于上述第二点，很简单，只需统计只有一个孩子结点的结点个数 k，则总共会有 2^k 种不同的二叉树

• 对于上述第一点，上述不建树的做法就已经行不通了，那就只能按照上述模拟建树的方法，真的建树！本题建树的具体代码如下。

The Codes - build the Tree :

#include<bits/stdc++.h>
using namespace std ;
struct Node{
	int val ;
	Node* lchild ;
	Node* rchild ;
}; 
Node* newNode(int x){
	Node* root = new Node ;
	root->val = x ;
	root->lchild = root->rchild = NULL ;
	return root ;
}
int n ;
bool isUnique = true ;
vector<int> pre , in , post ;
// int hdft = 0 ; //  How Many Different Trees
Node* createFormPreAndPost(int preL , int preR , int postL , int postR){
	if(preL == preR) return newNode(pre[preL]) ;
	if(pre[preL] == post[postR]){
		int k = preL + 1 , numLeft ;
		Node* root = newNode(post[postR]) ;
		while(pre[k] != post[postR - 1]) k ++ ;
		numLeft = k - preL - 1 ;
		if(numLeft)
			root->lchild = createFormPreAndPost(preL + 1 , k - 1 , postL , postL + numLeft - 1) ;
		else isUnique = false ; //  hdft ++
		root->rchild = createFormPreAndPost(k , preR , postL + numLeft , postR - 1) ;
		return root ;
	} 
}
void inorder(Node* root){
	if(root == NULL) return ;
	inorder(root->lchild) ;
	in.push_back(root->val) ;
	inorder(root->rchild) ;
}
int main(){
	scanf("%d" , &n) ;
	pre.resize(n) ;
	post.resize(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 = createFormPreAndPost(0 , n - 1 , 0 , n - 1) ;
	printf("%s\n" , isUnique?"Yes":"No") ;
	inorder(root) ;
	for(int i = 0 ; i < n ; i ++)
		printf("%d%c" , in[i] , ((i == n - 1)?'\n':' ')) ;
    // hdft = pow(2 , hdft) ; // 总的不同的二叉树的数量
   
	return 0 ;
}