leetcode-654-最大二叉树

题目:
给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
二叉树的根是数组中的最大元素。
左子树是通过数组中最大值左边部分构造出的最大二叉树。
右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树，并且输出这个树的根节点。

Example 1:
输入: [3,2,1,6,0,5]
输入: 返回下面这棵树的根节点：

注意:
给定的数组的大小在 [1, 1000] 之间。

解析:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
        time complexity : O(n)
        
        1.新建一个stk vector类型栈
        2.生成node
        3.stk为空或当前节点node小于stk顶层节点,则stk顶层节点的右子树设为当前node,并将node插入stk中
        4.若不满足,依次pop stk中元素 ,直到满足条件,并将当前节点的右子树设为最后一个pop的节点
        注意:stk是严格按照将降序排列的
 * };
 */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        vector<TreeNode *> stk;//按降序排列   栈底元素最大
        for(const auto num : nums){
            TreeNode*  node = new TreeNode(num);
            while(!stk.empty() && stk.back()->val < num){  //stk中最大值小于当前节点
                node->left = stk.back();    
                stk.pop_back();
            }
            if(!stk.empty()){
                stk.back()->right = node;
            }
            stk.push_back(node);
        }
        return stk[0];   //stk是按照降序排列的,栈顶元素就最大值
    }
};