中序遍历不一样啊
第一个是21354
第二个是12354
by minstdfx @ 2019-05-17 21:57:01
> 试求一棵符合**中序遍历**为（1,2,3,…,n）且加分最高的二叉树tree.
by minstdfx @ 2019-05-17 21:58:12
@[用户名已丢失](/space/show?uid=100250)
```cpp
3
/\
1 4
\ \
2 5
```
```cpp
3
/\
1 5
\ /
2 4
```
一样
by xh39 @ 2019-05-17 22:26:27
那前序遍历不是都是12345吗.....
by minstdfx @ 2019-05-18 09:03:47
@[用户名已丢失](/space/show?uid=100250)
不一样,一个是3 1 2 4 5,一个是3 1 2 5 4
by xh39 @ 2019-05-18 10:23:36
诶 我刚好也做到这 遇到一样的困扰了 我自己也提了个问题。
by 断罪之翼 @ 2019-05-18 10:51:46
看了下其他人的问题，这道题要求如果结果不唯一，字典序输出，也就是递归算法，子树退化成两个节点，以左节点为根，右节点为右子树输出
by 断罪之翼 @ 2019-05-18 10:55:29
## 哪位大佬看一下问题呀
## 总是输出不出来
```cpp
#include<iostream>
#include<cstdio>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<cstring>
#include<string.h>
#include<iomanip>
int n,a[40],root[40][40];
long long dp[40][40];
long long dfs(int l,int r)
{
if(l>r)return 1;
if(dp[l][r])return dp[l][r];
long long maxn=0;
for(int i=l;i<=r;i++)
{
long long t=dfs(l,i-1)*dfs(i+1,r)+a[i];
if(t>maxn)
{
maxn=t;
root[l][r]=i;
}
}
return dp[l][r]=maxn;
}
void dg(int l,int r)
{
if(l>r)return;
std::cout<<root[l][r]<<" ";
dg(l,root[l][r]-1);
dg(root[l][r]+1,r);
}
int main()
{
std::scanf("%d",&n);
for(int i=1;i<=n;i++)
{
std::scanf("%d",a[i]);
dp[i][i]=a[i];
root[i][i]=i;
}
std::cout<<dfs(1,n)<<"\n";
dg(1,n);
return 0;
}
```
by BotTleR @ 2020-02-21 13:23:31