# （算法）构造MaxTree

## 代码：

```#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=0;i<n;i++)
tree[i]=new Node(A[i],i);

for(int i=0;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]=-1;
}
else
lMax[i]=-1;
leftStk.push(tree[i]);
}

for(int i=n-1;i>=0;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]=-1;
}
else
rMax[i]=-1;
rightStk.push(tree[i]);
}

int root=0;
for(int i=0;i<n;i++){
if(lMax[i]==-1 && rMax[i]==-1){
root=i;
continue;
}

int parent;
if(lMax[i]==-1)
parent=rMax[i];
else if(rMax[i]==-1)
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=0;i<n;i++)
cin>>A[i];
Node* root=MaxTree(A,n);
PreOrderTraverse(root);
cout<<endl;
}
return 0;
}```

原文作者：AndyJee
原文地址: https://www.cnblogs.com/AndyJee/p/4849815.html
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。