7-5 Tree Traversals Again

发表于 更新于 阅读次数： 本文字数： 2.4k 阅读时长 ≈ 2 分钟

7-5 Tree Traversals Again
https://pintia.cn/problem-sets/16/problems/667

思路

这道题乍看有点奇怪，感觉堆栈弹出的数字顺序比较特殊，在纸上写写画画，然后发现这是树的中序遍历。因为题目中讲“Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations”但是只有前序中序后序中的一种是不能唯一确定一棵二叉树的，至少需要两种才可以，并且题目要求输出树的后序遍历，所以大胆猜测可能堆栈的这些操作隐含了另一个次序（也就是前序）的遍历，仔细看入栈顺序，发现原来入栈顺序是前序遍历。
后面就很好办了，根据处理得到的前序遍历和中序遍历，对这棵二叉树进行重建，然后进行后序遍历就可以得到结果。

注意

写代码应该细心，尤其是根据前序、中序重建二叉树的部分。首先是考虑到边界条件，即返回叶子节点的情况；其次要仔细考虑递归的调用，也就是从本次的前序、中序遍历结果分别推导出左右子树的前序、中序遍历结果，并将其作为递归调用的参数。
我在写重建二叉树时，不仅排查了半天bug，然后发现右子树的递归调用结果也赋值给了左子树（因为这行代码是从左子树赋值那里复制过来的，忘了改），而且后面发现右子树的递归调用还写错了一点。（🤡竟是我自己😅）

代码

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

using  node  = struct Node;
using tree = node * ;
struct Node
{
	int data;
	tree left;
	tree right;
};

void read(vector<int>& pre, vector<int>& in) {
	stack<int> stk;
	int n, m;
	cin >> n;
	m = n * 2;
	while (m--)
	{
		string str;//"Push" or "Pop"
		cin >> str;
		if (str=="Push")
		{
			int a;
			cin >> a;
			pre.push_back(a);
			stk.push(a);
		}
		if (str=="Pop")
		{
			int p = stk.top();
			stk.pop();
			in.push_back(p);
		}

	}

}

tree create(const vector<int>::iterator pre, const  vector<int>::iterator in, int size) {
	if (size==0)
	{
		return NULL;
	}
	else if (size==1)
	{
		tree T = new node;
		T->data = *pre;
		T->left = NULL;
		T->right = NULL;
		return T;
	}

	tree T = new node;
	int root = *pre;
	auto it = find(in, in+size, root);
	if (it == in + size)
	{
	    throw exception("not find");//正常情况下是不应该找不到的，可以根据异常排查错误
	}
	else
	{
		T->data = root;
		int newSize = it - in; //根节点到中序第一个节点的位置，获得左子树的节点数
		T->left = create(pre+1,in,newSize );
		T->right = create(pre+newSize+1, it+1, size -newSize-1);
	}
	
	return T;
}


bool first =1;
void printPostOrder(tree T) {
	if (T==NULL)
	{
		return;
	}
	if (T->left)
		printPostOrder(T->left);
	if (T->right)
		printPostOrder(T->right);
	if (!first)
	{
		cout << " ";
	}
	else
	{
		first = 0;
	}
	cout << T->data;

}

int main()
{
	vector<int> preOrder;
	vector<int> inOrder;
	
	read(preOrder, inOrder);

	tree T = create(preOrder.begin(), inOrder.begin(), preOrder.size());
	printPostOrder(T);

	return 0;
}