给出后序和中序遍历序列，求出只有左子树和只有右子树的结点之差
1 #include<bits/stdc++.h>
2 using namespace std;
3 int n;
4 int nl = 0, nr =0;
5 struct node{
6 int data, lchild = -1, rchild = -1;
7 };
8 vector<node> nodes(1005);
9 vector<int> in_order, post_order;
10 // 段错误代码，不知为何
11 // string in_order,post_order;
12 // vector<char> tree(1000, ' ');
13 // void rebuild(int p, char root, string in) {
14 // tree[p] = root;
15 // if (in.length() <= 1){
16 // return ;
17 // }
18 // string in_left = in.substr(0, in.find(root));
19 // string in_right = in.substr(in.find(root) + 1);
20 // for (int i = n - 1; i >= 0; -- i) {
21 // if (in_left.find(post_order[i])) {
22 // rebuild(p * 2, post_order[i], in_left);
23 // break;
24 // }
25 // }
26 // for (int i = n - 1; i >= 0; -- i) {
27 // if (in_right.find(post_order[i])) {
28 // rebuild(p * 2 + 1, post_order[i], in_right);
29 // break;
30 // }
31 // }
32 // }
33 int rebuild(int il, int ir, int pl, int pr) {
34 if (il > ir || pl > pr) {
35 return -1;
36 }
37 int root = post_order[pr];
38 int index;
39 for (index = il; index <= ir; ++ index) {
40 if (in_order[index] == root) {
41 break;
42 }
43 }
44 nodes[root].lchild = rebuild(il, index - 1, pl, pl + index - il - 1);
45 nodes[root].rchild = rebuild(index + 1, ir, pl + index - il, pr - 1);
46 return root;
47 }
48 void dfs(int p) {
49 bool hasleft = false, hasright = false;
50 if (nodes[p].lchild != -1) {
51 hasleft = true;
52 dfs(nodes[p].lchild);
53 }
54 if (nodes[p].rchild != -1) {
55 hasright = true;
56 dfs(nodes[p].rchild);
57 }
58 if (hasleft && !hasright) {
59 nl ++;
60 }
61 if (!hasleft && hasright) {
62 nr ++;
63 }
64 }
65 int main() {
66 cin >> n;
67 int temp;
68 for (int i = 0; i < n; ++ i) {
69 cin >> temp;
70 post_order.push_back(temp);
71 }
72 for (int i = 0; i < n; ++ i) {
73 cin >> temp;
74 in_order.push_back(temp);
75 }
76 int root = rebuild(0, n-1, 0, n-1);
77 dfs(root);
78 cout << root << endl;
79 cout << nl - nr << " = " << nl << " - " << nr;
80
81 }
82
标签：Skewness,PAT,temp,int,rebuild,二叉树,post,root,order From： https://www.cnblogs.com/coderhrz/p/18595932