LeetCode 654 最大二叉树

654.最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

1. 创建一个根节点，其值为 nums 中的最大值。
2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。

1.1 DFS实现

直接根据题设的最大二叉树的定义进行构造，构造的过程是递归的，每次需要在指定的序列中寻找最大值，也就是 的时间复杂度。

class Solution {
public:
    pair<int,int> getMax(vector<int> nums,int start,int end){
        pair<int,int> max={nums[start],start};
        for(int i=start+1;i<=end;i++)
        max=nums[i]>max.first?make_pair(nums[i],i):max;
        return max;
    }
    void build(TreeNode* &root,vector<int>nums,int start,int end){
        if(start<=end){
            pair<int,int> max=getMax(nums,start,end);
            root=new TreeNode(max.first);
            build(root->left,nums,start,max.second-1);
            build(root->right,nums,max.second+1,end);
        }
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode *root=nullptr;
        build(root,nums,0,nums.size()-1);
        return root;
    }
};

1.2 单调栈实现

将构造的过程转化为基于节点数和数组实现：

1. 初始时，我们只有一个根节点，其中存储了整个数组；
2. 在每一步操作中，我们可以「任选」一个存储了超过一个数的节点，找出其中的最大值并存储在该节点。最大值左侧的数组部分下放到该节点的左子节点，右侧的数组部分下放到该节点的右子节点；
3. 如果所有的节点都恰好存储了一个数，那么构造结束。

此处，在题解中提出，在进行树的构造过程中，并不需要按照最大二叉树的定义进行构造，实际上在上述的定义中，存在一个特性：对于最大的节点一定是根节点，第二大的节点则一定是根节点的左/右孩子，但是对于第三大的节点就存在不确定性。

构造方式：每次选择数组中值最大的那个节点进行构造。这样一来，我们就可以保证按照数组中元素降序排序的顺序依次构造每个节点。当选择节点中的数组最大值为nums[i]时，说明大于nums[i]的元素已经全部构造，小于的元素还没有构造。

在最终构造出的树上，以nums[i] 为根节点的子树，在原数组中对应的区间，左边界为nums[i] 左侧第一个比它大的元素所在的位置，右边界为nums[i] 右侧第一个比它大的元素所在的位置。左右边界均为开边界。如果某一侧边界不存在，则那一侧边界为数组的边界。如果两侧边界均不存在，说明其为最大值，即根节点。

并且nums[i] 的父结点是两个边界中较小的那个元素对应的节点

此处的思想就是，先找到相应的元素，然后确定当前元素在原来序列中的划分边界，并且有nums[i] 的父结点是两个边界中较小的那个元素对应的节点（左右孩子的问题则需要根据边界的位置来进行确定）

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        int n = nums.size();
        vector<int> stk;
        vector<int> left(n, -1), right(n, -1); // 存储边界的数组
        vector<TreeNode*> tree(n); // 保存树的节点
        for (int i = 0; i < n; ++i) {
            tree[i] = new TreeNode(nums[i]);
            while (!stk.empty() && nums[i] > nums[stk.back()]) { // 当前元素大于栈顶元素
                right[stk.back()] = i; //对于栈顶元素而言，右侧第一个大于自己的元素找到了
                stk.pop_back();
            }
            if (!stk.empty()) {// 栈非空，说明此时栈顶元素大于当前元素，并且栈顶元素在当前元素的左边
                left[i] = stk.back(); // 记录当前元素的左边界
            }
            stk.push_back(i); //将元素索引入栈
        }
        // 找到左右边界之后进行处理，此处就只需要顺序便利即可
        TreeNode* root = nullptr;
        for (int i = 0; i < n; ++i) {  // 本质上只需要在tree数组中进行便利
            if (left[i] == -1 && right[i] == -1) { // 根节点
                root = tree[i];
            }
            else if (right[i] == -1 || (left[i] != -1 && nums[left[i]] < nums[right[i]])) {
                tree[left[i]]->right = tree[i];
            }
            else {
                tree[right[i]]->left = tree[i];
            }
        }
        return root;
    }
};

将上述实现改写为单调栈实现：

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        int n = nums.size();
        vector<int> stk;
        vector<TreeNode*> tree(n);
        for (int i = 0; i < n; ++i) {
            tree[i] = new TreeNode(nums[i]);
            while (!stk.empty() && nums[i] > nums[stk.back()]) {
                tree[i]->left = tree[stk.back()]; // 对于栈顶而言，当前元素i是自己的右边第一个比自己大的元素
                stk.pop_back();
            }
            if (!stk.empty()) { // 此时while循环不管有没有开始，都说明一个问题，栈顶元素是大于当前元素
                tree[stk.back()]->right = tree[i]; // 对于节点i而言，当前栈顶元素是自己的左边第一个比自己大的元素
            }
            stk.push_back(i);
        }
        return tree[stk[0]];
    }
};