Problem P01. [算法课分治] 最大二叉树

需要注意的：

1. scanf()的返回值是 EOF，输入结束
2. 通过指针指向左右子树的二叉树构建

#include<iostream>
#include<bits/stdc++.h>
#include<cstdio>

using namespace std;
struct node
{
    int data;
    node *leftchild;
    node *rightchild;

    node(const int& x){
        data = x;
        leftchild=NULL;
        rightchild=NULL;
    }
};

int nums[1005];
node* buildtree(int left, int right){
    if (left>right) return NULL;
    int idmax = left, valmax = nums[idmax];
    for (int i = left+1; i <= right; i++){
        if (valmax<nums[i]){
            valmax = nums[i];
            idmax = i;
        }
    }
    node* root = new node(valmax);
    //cout << root->data << endl;
    root->leftchild = buildtree(left, idmax-1);
    root->rightchild = buildtree(idmax+1, right);
    return root;
}

void qiansearch(node *root)
{
    printf("%d ", (root->data));
    if (root->leftchild==NULL && root->rightchild==NULL){
        return;
    }
    if (root->leftchild==NULL){
        printf("null ");
    }else {
        qiansearch(root->leftchild);
    }
    if (root->rightchild==NULL){
        printf("null ");
    }else {
        qiansearch(root->rightchild);
    }
    return;
}

int main()
{
    int n;
    for(n = 0; 1; n++)
    {
        int ret = scanf("%d", &nums[n]);
        if (ret == EOF)break;
    }
    n--;
    node *root = buildtree(0, n);
    qiansearch(root);
    return 0;
}