LeetCode·每日一题·654.最大二叉树·递归·单调栈

链接：https://leetcode.cn/problems/maximum-binary-tree/solution/-by-xun-ge-v-qf9i/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

示例

思路

解题思路
对于树的相关问题->用递归基本上都能解决

【递归构造】
题意需要构造一个最大二叉树，规则为：

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

题目都告诉我们怎么递归了，直接根据题意递归构造即可

时间复杂度为O(n^2)，使用单调栈优化为O(n)

【单调栈】

边遍历边构造二叉树的各个节点，使用一个递减的单调栈来存储元素，最后，栈底的元素就是整个二叉树的最大值，也就是根节点。

以 [3,2,1,6,0,5] 为例：

• 构造节点 3，入栈；
• 构造节点 2，它比栈顶元素 3 小，所以，它是 3 的右子节点，直接入栈；
• 构造节点 1，它比栈顶元素 2 小，所以，它是 2 的右子节点，直接入栈；
• 构造节点 6，它比栈顶元素 1 大，所以，1 是它的左子节点，弹出 1；同样地，栈顶元素 2 也比它小，弹出 2 并做为它的左子节点；把栈顶所有比它小的元素都弹出，最后弹出的是 3，所以，最终是 3 做为 6 的左子节点，并把 6 入栈；
• 构造节点 0，它比栈顶元素 6 小，所以，它是 6 的右子节点，直接入栈；
• 构造节点 5，它比栈顶元素 0 大，所以，0 是它的左子节点，弹出 0；接着比较，它比栈顶元素 6 小，所以，它是 6 的右子节点，入栈；
• 最后，栈中元素为 [6,5]，栈底元素为 6，是最终的根节点；

代码

【递归构造】

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode * dfsCreateTree(int * nums, int left, int right)
{
    if(left >= right)
    {
        return NULL;
    }
    int max = -1;
    int index = left;
    for(int i = left; i < right; i++)//寻找最大值，并保存下标
    {
        if(nums[i] > max)
        {
            index = i;
            max = nums[i];
        }
    }
    struct TreeNode * root = malloc(sizeof(struct TreeNode));//构造节点
    root->val = max;//赋值
    root->left = dfsCreateTree(nums, left, index);//递归构造左右节点
    root->right = dfsCreateTree(nums, index+1, right);
    return root;
}
 
struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize){
    return dfsCreateTree(nums, 0, numsSize);//递归构造树
}
 
作者：xun-ge-v
链接：https://leetcode.cn/problems/maximum-binary-tree/solution/-by-xun-ge-v-qf9i/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

【单调栈】

struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize){
    struct TreeNode * ans[numsSize];//定义单调栈
    int top = -1;
    for(int i = 0; i < numsSize; i++)//遍历所有节点
    {
        struct TreeNode * n = malloc(sizeof(struct TreeNode));//创建节点
        n->val = nums[i];
        n->left = NULL;
        n->right = NULL;
        while(top != -1 && ans[top]->val < n->val)//出栈并将栈顶元素赋为当前元素的左子节点
        {
            n->left = ans[top];
            --top;
        }
        if(top != -1)//递减，是栈顶元素的右子节点
        {
            ans[top]->right = n;
        }
        ans[++top] = n;//入栈
    }
    return ans[0];
}
 
作者：xun-ge-v
链接：https://leetcode.cn/problems/maximum-binary-tree/solution/-by-xun-ge-v-qf9i/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。