左神算法进阶班3_1构造数组的MaxTree

缺乏、安全感 2022-10-02 15:55 87阅读 0赞

## 题目 ##

一个数组的MaxTree定义：

*  数组必须没有重复元素
 *  MaxTree是一棵二叉树，数组的每一个值对应一个二叉树节点
 *  包括MaxTree树在内且在其中的每一棵子树上，值最大的节点都是树的头

给定一个没有重复元素的数组arr，写出生成这个数组的MaxTree的函数，要求如果数组长度为N，则时间负责度为O(N)、额外空间负责度为O(N)。

## 实现思路 ##

将数组按照大根堆进行排序  
　　然后直接按照大根堆进行构造一颗二叉树即可。  
　　使用单调栈  
　　通过使用单调栈，将数组中中所有数的左右比他大的数记录下来  
　　当某个数既无左边比他大的数，有无右边比他大的数，则该数为全局最大，将其作为二叉树的根  
　　然后，某数只有左比他大的数，或者右比他大的数，则该数直接挂在比他大的数的下面，  
　　当某个数既有左比他大的数，又有右比他大的数，则挂在两个数中较小数的下面。  
　　然后直接构成一棵树。  
　　右大值为右孩子，左大值为左孩子

## 代码 ##

1 void creatMaxTree(Node*& root, vector<int>v)
     2 {
        //以下代码都是以数组的下角标为根据
     3     vector<Node*>node;
     4     vector<pair<int, int>>res;//存储每个数的左右大小的数
     5     res.resize(v.size());    
     6     deque<int>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<int, int>(-1, i);
    17             else//有右大值和左大值
    18                 res[index] = pair<int, int>(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<int, int>(-1, -1);
    28         else//无右大值有左大值
    29             res[index] = pair<int, int>(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         else
    45             node[a]->lchild = node[i];
    46     }    
    47 }

## 效果 ##

The shape of tree is:
    =============================================================
                              v5v
                                                                v3v
                                               ^4^
                                                                ^2^
             H6H
                              ^1^
    =============================================================

转载于:https://www.cnblogs.com/zzw1024/p/11052016.html