首页 > 其他分享 >Day47 代码随想录打卡|二叉树篇---最大二叉树

Day47 代码随想录打卡|二叉树篇---最大二叉树

时间:2024-06-09 11:59:09浏览次数:33  
标签:node 递归 nums maxValueIndex 随想录 二叉树 数组 打卡

题目(leecode T654):

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

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

返回 nums 构建的 最大二叉树 

方法:本题可以看出是按照同一个处理原则的重复处理,因此还是用递归法比较方便。确定三要素

1:传入参数和返回值,因为给定的是一个数组。所以我们传入的参数就是数组,而我们要返回的是一个构造好的树,因此返回值是存储树节点的指针

2:确定终止条件,因为题目中已经表示数组不会为空,因此当数组元素只剩一个时,代表该元素是树的叶子节点,到这里就可以结束了。

3:确定单层的处理逻辑,每一层中我们要处理的是,我们要找到当数组中最大的元素,用该元素来构造根节点,然后该元素左半部分继续递归生成左子树,右半部分继续递归生成右子树。

题解:
 

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode* node = new TreeNode(0);
        if(nums.size() == 1){
            node -> val = nums[0];
            return node;
        }
        int maxValue = 0;                                //找数组最大的元素当根节点
        int maxValueIndex = 0;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] > maxValue){
                maxValue = nums[i];
                maxValueIndex = i;
            }
        }
        node->val = maxValue;
        if(maxValueIndex > 0){                           //切分左子树
            vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);
            node -> left = constructMaximumBinaryTree(newVec);  //递归生成左子树
        }
        if(maxValueIndex < (nums.size() - 1)){           //切分右子树
            vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());
            node ->right = constructMaximumBinaryTree(newVec);  //递归生成右子树
        }
        return node;
    }
};

标签:node,递归,nums,maxValueIndex,随想录,二叉树,数组,打卡
From: https://blog.csdn.net/m0_48909584/article/details/139558622

相关文章

  • 二叉树小结
    目录简介二叉树的种类在实际开发中评估二叉树的性能搜索二叉树代码实现二叉树堆的实现红黑树简介简介二叉树是一种特殊的树,每个节点最多有两个子节点,通常被称为左子节点和右子节点。它是计算机科学中的一种基础且重要的树形结构,被广泛应用在各种算法和数据结构中。二......
  • 打卡信奥刷题(67)用Scratch图形化工具信奥P1125 [NOIP2008 提高组] 笨小猴,写了一个好用
    [NOIP2008提高组]笨小猴题目描述笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用这种方法去选择选项的时候选对的几率非常大!这种方法的具体描述如下:假设maxn......
  • 代码随想录算法训练营 day31 | 455.分发饼干 376.摆动序列 53.最大子数组和
    376.摆动序列说实话,没明白为啥算是贪心。最开始的思路是去重,然后统计正负变化次数。classSolution{public:intwiggleMaxLength(vector<int>&nums){if(nums.size()==1)return1;intans=0,last=-2,now;for(inti=1;i<nums.size();......
  • 代码随想录第4天 | 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题 0
    题目:24.两两交换链表中的节点思路:设置虚拟头结点,双指针+临时指针,(感觉也能递归,未尝试)时间复杂度:O(n)空间复杂度:O(1)坑:1.又忘了else{}和return2.试图访问空指针,多个条件的顺序问题及"&&""||"问题,cur->next要写在cur->next->next前面/***Definitionforsingly-linked......
  • 代码随想录算法训练营第三十二天 | 122.买卖股票的最佳时机 55.跳跃游戏 45.跳跃游戏I
    122.买卖股票的最佳时机II题目链接文章讲解视频讲解思路:每次记录当天的股票价格,如果下一天比今天的价钱高那么今天就买,这样保证每一次买股票都是赚的否则记录下一天的股票,因为下一天的股票比今天的便宜,下一天买比今天买划算classSolution{public:intmaxProfit(v......
  • 【力扣】二叉树的最大深度
    给定一个二叉树root,返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。示例1:输入:root=[3,9,20,null,null,15,7]输出:3示例2:输入:root=[1,null,2]输出:2层序遍历求深度流程层序遍历是对二叉树每一层进行遍历,我们定义一个......
  • 【力扣】对称二叉树
    给你一个二叉树的根节点root,检查它是否轴对称。示例1:输入:root=[1,2,2,3,4,4,3]输出:true示例2:输入:root=[1,2,2,null,3,null,3]输出:false队列层序遍历流程进行两次同步遍历,分别从根节点的左子树和右子树开始,然后比较每个节点的值代码实现classSolution......
  • 【力扣】翻转二叉树
    给你一棵二叉树的根节点root,翻转这棵二叉树,并返回其根节点。示例1:输入:root=[4,2,7,1,3,6,9]输出:[4,7,2,9,6,3,1]示例2:输入:root=[2,1,3]输出:[2,3,1]示例3:输入:root=[]输出:[]递归法流程把每一个节点的左右孩子互换,就实现了整体翻转的效果。使用递归......
  • 代码随想录算法训练营第四天 |
    24.两两交换链表中的节点题目:给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。解题:关键:cur的位置在要交换的两个节点的前面具体如何交换的操作!!while种植条件:cur的下一个和下下个都不为空,不......
  • 代码随想录算法训练营第四天 Leetcode 24 两两交换链表节点 Leetcode19 删除链表倒数
    链表问题首先要记住设置虚拟头节点Leetcode24两两交换链表节点题目链接思路:就是简单模拟两两交换 要注意链表节点的处理一定要获取到合适的位置比如:这一题中两个交换节点的前一个节点注意链表保存临时节点/***Definitionforsingly-linkedlist.*publicclas......