首页 > 其他分享 >LeetCode/最大二叉树

LeetCode/最大二叉树

时间:2022-08-20 01:11:08浏览次数:63  
标签:right TreeNode 最大 nums int 二叉树 root LeetCode left

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

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

1. 暴力分治构造

暴力在于每次递归都要找一次最大值

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return construct(nums, 0, nums.size() - 1);
    }
    //分治构造子树
    TreeNode* construct(const vector<int>& nums, int left, int right) {
        if (left > right) return nullptr;//边界条件,相等时还需要构建单个节点
        int best = left;//记录最大值位置
        for (int i = left + 1; i <= right; ++i) 
            if (nums[i] > nums[best]) 
                best = i;
        TreeNode* node = new TreeNode(nums[best]);
        node->left = construct(nums, left, best - 1);
        node->right = construct(nums, best + 1, right);
        return node;
    }
};

2. 顺序更新树

实现最大数的插入值方法,便可以顺序建树

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode* root = nullptr;
        for(int val:nums)
            root = insertIntoMaxTree(root,val);
        return root;
    }
    //一个一个插入更新
    TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
        if(!root) return new TreeNode(val);
        if(root->val<val)//如果该值大于根节点值,该值作为根节点,原树作为左子树
            return new TreeNode(val,root,nullptr);
        else //放到右子树递归构造
            root->right = insertIntoMaxTree(root->right,val);
        return root;
    }
};

3. 单调栈

暴力构造的时候,会有重复的遍历找最值,可以通过单调栈一次遍历
本质上是找每个元素左侧和右侧第一个比它大的元素

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        int n = nums.size();
        stack<int> s;//单调栈
        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 (!s.empty() && nums[i] > nums[s.top()]) {//单调栈消消乐
                right[s.top()] = i;
                s.pop();
            }//该值就是他们的右侧第一个更大值
            if (!s.empty())  left[i] = s.top();//同时得到该元素左侧第一个更大值
            s.push(i);//入栈
        }

        TreeNode* root = nullptr;
        //构建各节点的链接关系
        for (int i = 0; i < n; ++i) {//从左往右遍历
            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;
    }
};

标签:right,TreeNode,最大,nums,int,二叉树,root,LeetCode,left
From: https://www.cnblogs.com/929code/p/16607013.html

相关文章

  • 网络最大流三题
    昨天杭电多校1001题人均过,该学学网络流了(虽然dls说过,网络流只能出金牌题)在b站看了电子科大的网络流入门,学会了dinic的板子,还不会严格证明求单源单汇的最大流,简单来说就是......
  • 【LeetCode】102.二叉树的层序遍历
    【LeetCode】102.二叉树的层序遍历/**转载请说明出处与作者*作者:多巴胺dopamine*/一问题描述1题目给你二叉树的根节点root,返回其节点值的层序遍历。(即......
  • 436. 寻找右区间--LeetCode_二分
    来源:力扣(LeetCode)链接:https://leetcode.cn/problems/find-right-interval著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。题目大意是这样的 数组......
  • leetcode 225. Implement Stack using Queues 用队列实现栈(简单)
    一、题目大意请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop和empty)。实现MyStack类:voidpush(intx)将元素x压入栈顶。......
  • [Oracle] LeetCode 848. Shifting Letters
    YouaregivenastringsoflowercaseEnglishlettersandanintegerarrayshiftsofthesamelength.Calltheshift()ofaletter,thenextletterinthealph......
  • 练习8:最大公约数和最小公倍数问题
    最大公约数的计算,用到辗转相除法例如:求gcd(24,10),可以转换为gcd(10,4),然后是gcd(4,2),然后是(2,0),最好得出结果是2方法1:functiongcd(a,b){vartempif......
  • 2022-8-19 剑指offer-二叉树-递归
    剑指OfferII055.二叉搜索树迭代器难度中等30收藏分享切换为英文接收动态反馈实现一个二叉搜索树迭代器类BSTIterator ,表示一个按中序遍历二叉搜索树(BST)的迭代......
  • 275. H 指数 II--Leetcode_二分
    来源:力扣(LeetCode)链接:https://leetcode.cn/problems/h-index-ii著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。题目的大意是这样的 有一个升序......
  • leetcode264-丑数 II
    丑数II优先队列维护一个优先队列。先取出最小的数字,将其乘以2、3、5,如果发现没有重复的话就装入优先队列中,需要用到set进行去重。classSolution{publicintn......
  • 275. H 指数 II--Leetcode_暴力
    来源:力扣(LeetCode)链接:https://leetcode.cn/problems/h-index-ii著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。题目的大意是这样的 有一个升序......