题目
一个数组的MaxTree定义：
- 数组必须没有重复元素
- MaxTree是一棵二叉树，数组的每一个值对应一个二叉树节点
- 包括MaxTree树在内且在其中的每一棵子树上，值最大的节点都是树的头
给定一个没有重复元素的数组arr，写出生成这个数组的MaxTree的函数，要求如果数组长度为N，则时间负责度为O(N)、额外空间负责度为O(N)。
实现思路
将数组按照大根堆进行排序
然后直接按照大根堆进行构造一颗二叉树即可。 使用单调栈 通过使用单调栈，将数组中中所有数的左右比他大的数记录下来 当某个数既无左边比他大的数，有无右边比他大的数，则该数为全局最大，将其作为二叉树的根 然后，某数只有左比他大的数，或者右比他大的数，则该数直接挂在比他大的数的下面， 当某个数既有左比他大的数，又有右比他大的数，则挂在两个数中较小数的下面。 然后直接构成一棵树。 右大值为右孩子，左大值为左孩子代码
1 void creatMaxTree(Node*& root, vector v) 2 { //以下代码都是以数组的下角标为根据 3 vector node; 4 vector >res;//存储每个数的左右大小的数 5 res.resize(v.size()); 6 deque d;//单调栈 7 for (int i = 0; i < v.size(); ++i) 8 { 9 Node* p = new Node(v[i]);10 node.push_back(p);//先生成相关的节点11 while (!d.empty() && v[i] > v[d.back()])12 {13 int index = d.back();14 d.pop_back();15 if (d.empty())//有右大值，无左大值16 res[index] = pair (-1, i);17 else//有右大值和左大值18 res[index] = pair (d.back(), i);19 }20 d.push_back(i);21 }22 while (!d.empty())23 {24 int index = d.back();25 d.pop_back();26 if (d.empty())//即无右大值，又无左大值27 res[index] = pair (-1, -1);28 else//无右大值有左大值29 res[index] = pair (d.back(), -1);30 }31 for (int i = 0; i < res.size(); ++i)32 {33 int a, b;34 a = res[i].first;35 b = res[i].second;36 if (a == -1 && b == -1)//即无右大值，又无左大值为根节点37 root = node[i];38 else if (a == -1 && b != -1)39 node[b]->rchild = node[i];40 else if (a != -1 && b == -1)41 node[a]->lchild = node[i];42 else if (v[a] > v[b])43 node[b]->rchild = node[i];44 else45 node[a]->lchild = node[i];46 } 47 } 效果
The shape of tree is:============================================================= v5v v3v ^4^ ^2^ H6H ^1^=============================================================