题意:
分别用中序和后序输入一颗有权二叉树的权值,找出叶子满足到根权值和最小,如果一样大选自身权值最小的叶子
要点:
后序的最后一个结点一定是根结点,再在中序中找对应权值相同的结点的位置,这样左边就是左子树,右边是右子树,再递归一个个把分别的根结点放上去,这就是后序如何变成中序。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<ctype.h>
#define min(a,b) a>b?b:a
#define maxn 100005
int v1[maxn], v2[maxn];
int ans, min_sum;int change(char *s,int v[])//将字符串转换为对应的数字
{int top=0;for (int i = 0; s[i]; i++) {while (s[i] == ' ')i++;v[top] = 0;while (s[i] && isdigit(s[i]))//isdigit判断是否为整数,头文件为ctype.h{v[top] = v[top] * 10 + s[i] - '0';i++;}top++;if (!s[i])//必要,有可能前面while时就跳出,s[i]为\0,如果没有会+1,反而跳过了break;}return top; //返回的是有几个结点,后面运算要-1
}
void build(int n,int *v1,int *v2,int sum)
{if (n <= 0) //这步是必要的,有时会出现左子树满足但右子树为空,这种情况直接返回return;int p;for (int i = 0; i <n; i++) //寻找后序最后一个在中序中的位置{if (v1[i] == v2[n-1]){p = i;break;}}sum += v2[n - 1];if (p <= 0 && n - p - 1 <= 0) //p和n-p-1分别代表左右子树中还有几个结点{if (sum == min_sum)ans = min(ans, v2[n - 1]);//如果权和相同就选权值小的结点else if (sum < min_sum){min_sum = sum;ans = v2[n - 1];}return;}build(p, v1, v2, sum);build(n - p - 1, v1+p+1, v2+p, sum);//这里注意从v2+p开始,那么再+n-p-1就是从n-1除开始,是正确的
}int main()
{char s[maxn];while (gets(s)){change(s, v1);gets(s);int last=change(s, v2);ans = min_sum = 1000000;build(last, v1, v2, 0);printf("%d\n", ans);}return 0;
}