最大二叉树(分治）

给定一个不含重复元素的整数数组 。以此数组直接递归构建的最大二叉树。最大二叉树定义如下：

• 二叉树的根是数组中的最大元素。
• 左子树是通过数组中最大值左边部分递归构造出的最大二叉树。
• 右子树是通过数组中最大值右边部分递归构造出的最大二叉树。

返回有给定数组构建的最大二叉树 。

输入：

输入一行多个数字代表数组。数字与数字之间用空格隔开。

以 EOF 作为结束输入

输出：

输出一行字符代表二叉树的构造结果（前序遍历）

#include<bits/stdc++.h>

using namespace std;
vector<int> a;

void solve(int be,int en)
{
    if(be==en)//遇到空节点输出null，返回
    {
        cout<<"null"<<" ";
        return ;
    }
    int maxa=INT_MIN;
    int maxi;
    for(int i=be;i<en;i++)//在每一个[be,en]区间找出最大值并且记录位置
    {
        if(a[i]>maxa)
        {
            maxa=a[i];
            maxi=i;
        }
    }
    cout<<maxa<<" ";//输出最大值
    if(be<maxi||maxi+1<en)//保证至少有一个非空叶子节点
    {
        solve(be,maxi);
        solve(maxi+1,en);
    }
}

int main()
{
    int b;
    char ch;
    int len=0;
    while(cin>>b)
    {
        a.push_back(b);
        len++;
        if((ch=getchar())=='\n')
        {
            break;
        }
    }
    solve(0,len);
}