首页 > itarticle > pat a1086题解

pat a1086题解

admin 11月 14, 2020 0

1086 Tree Traversals Again （25 分)

An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.

img
Figure 1

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: “Push X” where X is the index of the node being pushed onto the stack; or “Pop” meaning to pop one node from the stack.

Output Specification:

For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop

Sample Output:

1
 
3 4 2 6 5 1

题解：

题目说中序遍历二叉树可以用非递归栈的方法遍历。输入样例给你一组中序创建二叉树的栈操作，让你给出这棵数的后序遍历。我们可以把栈操作和图Figure 1结合起来很容易地发现，原来Push进栈的顺序为先序排列，而Pop出栈的顺序为中序排列。这样，求一个树的后序排列，简单一点只要根据先序和后序递归创建树，再用递归后序遍历就行了。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 

#include <malloc.h>
#include <stack>
#include <cstring>

using namespace std;

struct {
	int value;
	TreeNode* ltree;
	TreeNode* rtree; 
}; 

int num = 0;
void postorder(TreeNode* root, int n)
{
	if(root->ltree!=NULL)postorder(root->ltree, n);
	if(root->rtree!=NULL)postorder(root->rtree, n);
	printf("%d", root->value);num++;
	if(num<n)printf(" ");
	
}

void getPerAndIn(int* perorder, int* inorder, int n)
{
	stack<int> s;
	char str[10];
	int temp;
	int per = 0;
	int in = 0;
	n = 2*n;
	while(n--)
	{
		scanf("%s",str);
		if(strcmp(str, "Push") == 0)
		{
			scanf("%d", &temp);
			s.push(temp);
			perorder[per] = temp;
			per++;
		}
		else if(strcmp(str, "Pop") == 0)
		{
			inorder[in] = s.top();
			in++;
			s.pop();
		}
	}
	
}

void buildTree(int* perorder, int* inorder, int n, TreeNode** root)
{
	if(!perorder || !inorder || n <= 0)
		return;
	
	int i;
	for( i = 0; i < n; i++)
	{
		if(perorder[0] == inorder[i])
		{
			break;	
		} 
	}
	
	*root = (TreeNode*)malloc(sizeof(TreeNode));
	if(!root)
	{
		return;	
	} 
	(*root)->ltree = (*root)->rtree = NULL;
	(*root)->value = perorder[0];
	
	buildTree(perorder+1, inorder, i, &(*root)->ltree);
	buildTree(perorder+i+1, inorder+i+1, n-i-1, &(*root)->rtree);
	 
}
int main()
{
	int n, perorder[31], inorder[31];
	scanf("%d", &n);
	getPerAndIn(perorder, inorder, n);
	TreeNode* root; 
	buildTree(perorder, inorder, n, &root);
	postorder(root, n);
	
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能