思路:
虽然二叉树中有重复的元素,但是根据定义发现重复的元素只出现在其中一侧。
此题右子树所有节点值是大于等于根节点值,所以在中序遍历查找根节点是找的是第一次出现的位置。
而镜像之后,左子树所有节点值是大于等于根节点值,所以在中序遍历中查找根节点找的是最后一次出现位置。
当无法在中序遍历中找到根节点时说明建树不成功。
c++
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int preOrder[N], inOrder[N], postOrder[N];
int cnt;
bool build(int il, int ir, int pl, int pr,int type) {
if (il > ir) return true; //空树一定是可行的
int root = preOrder[pl];
int k;
if (type == 0) {
for (k = il; k <= ir; k ++)
if (inOrder[k] == root) break;
if (k > ir) return false;
} else { //镜像
for (k = ir; k >= il; k --) //从后往前找
if (inOrder[k] == root) break;
if (k < il) return false;
}
bool res = true;
if (!build(il, k - 1, pl + 1, pl + 1 + (k - 1 - il), type)) res = false;
if (!build(k + 1, ir, pl + 1 + (k - 1 - il) + 1, pr, type)) res = false;
postOrder[cnt++] = root;
return res;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i ++) {
cin >> preOrder[i];
inOrder[i] = preOrder[i];
}
sort(inOrder, inOrder + n);
if (build(0, n - 1, 0, n - 1, 0)) {
puts("YES");
cout << postOrder[0];
for (int i = 1; i < n; i++) cout << ' ' << postOrder[i];
cout << '\n';
} else {//镜像
reverse(inOrder, inOrder + n); //镜像后中序遍历是从大到小
cnt = 0; //cnt要重新清零,因为前面的build修改了cnt的值
if (build(0, n - 1, 0, n - 1, 1)) {
puts("YES");
cout << postOrder[0];
for (int i = 1; i < n; i++) cout << ' ' << postOrder[i];
cout << '\n';
} else {
puts("NO");
}
}
return 0;
}