（算法）构造MaxTree

题目：

给定一个没有重复元素的数组A，定义A上的MaxTree如下：MaxTree的根节点为A中最大的数，根节点的左子树为数组中最大数左边部分的MaxTree，右子树为数组中最大数右边部分的MaxTree。请根据给定的数组A，设计一个算法构造这个数组的MaxTree。

思路：

如果能够确定每个节点的父亲节点，则可以构造出整棵树。找出每个数往左数第一个比他大的数和往右数第一个比他大的数，两者中较小的数即为该数的父亲节点。如：[3,1,2]，3没有父亲节点，1的父亲节点为2，2的父亲节为3。并且可以根据与父亲的位置关系来确定是左儿子还是右儿子。接下来的问题是如何快速找出每个数往左、往右第一个比他大的数。这里需要用到数据结构栈。以找每个数左边第一个比他大的数为例，从左到右遍历每个数，栈中保持递减序列，新来的数不停的Pop出栈顶直到栈顶比新数大或没有数。以[3,1,2]为例，首先3入栈，接下来1比3小，无需pop出3，1入栈，并且确定了1往左第一个比他大的数为3。接下来2比1大，1出栈，2比3小，2入栈。并且确定了2往左第一个比他大的数为3。用同样的方法可以求得每个数往右第一个比他大的数。时间复杂度O(n)，空间复杂度也是O(n)为最优解法。

代码：

#include <iostream>

#include <vector>

#include <stack>

using namespace std;

struct Node{

    int val;

    int idx;

    Node *left;

    Node *right;

    Node(int v,int i):val(v),idx(i),left(NULL),right(NULL){}

};

void PreOrderTraverse(Node* root){

    if(root!=NULL){

        cout<< root->val <<" ";

        PreOrderTraverse(root->left);

        PreOrderTraverse(root->right);

    }

}

Node* MaxTree(const vector<int> &A,int n){

    stack<Node*> leftStk;

    stack<Node*> rightStk;

    vector<Node*> tree(n);

    vector<int> lMax(n);

    vector<int> rMax(n);

    for(int i=;i<n;i++)

        tree[i]=new Node(A[i],i);

    for(int i=;i<n;i++){

        if(!leftStk.empty()){

           while(!leftStk.empty() && leftStk.top()->val<A[i])

                leftStk.pop();

           if(!leftStk.empty())

                lMax[i]=leftStk.top()->idx;

           else

                lMax[i]=-;

        }

        else

            lMax[i]=-;

        leftStk.push(tree[i]);

    }

    for(int i=n-;i>=;i--){

        if(!rightStk.empty()){

            while(!rightStk.empty() && rightStk.top()->val<A[i])

                rightStk.pop();

            if(!rightStk.empty())

                rMax[i]=rightStk.top()->idx;

            else

                rMax[i]=-;

        }

        else

            rMax[i]=-;

        rightStk.push(tree[i]);

    }

    int root=;

    for(int i=;i<n;i++){

        if(lMax[i]==- && rMax[i]==-){

            root=i;

            continue;

        }

        int parent;

        if(lMax[i]==-)

            parent=rMax[i];

        else if(rMax[i]==-)

            parent=lMax[i];

        else

            parent=A[lMax[i]]<A[rMax[i]]?lMax[i]:rMax[i];

        if(i<parent)

            tree[parent]->left=tree[i];

        else

            tree[parent]->right=tree[i];

    }

/*

    for(int i=0;i<n;i++){

        cout<<tree[i]->idx <<":";

        if(tree[i]->left)

            cout<<"left: "<<tree[i]->left->idx<<" ";

        if(tree[i]->right)

            cout<<"right:"<<tree[i]->right->idx;

        cout<<endl;

    }

*/

    return tree[root];

}

int main()

{

    int n;

    while(cin>>n){

        vector<int> A(n);

        for(int i=;i<n;i++)

            cin>>A[i];

        Node* root=MaxTree(A,n);

        PreOrderTraverse(root);

        cout<<endl;

    }

    return ;

}