首页 > 其他分享 >代码随想录第十七天

代码随想录第十七天

时间:2024-11-04 10:47:07浏览次数:6  
标签:node TreeNode struct val 代码 随想录 第十七 root 节点

654.最大二叉树

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

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

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

示例 1:

输入:nums = [3,2,1,6,0,5]
输出:[6,3,5,null,2,0,null,null,1]
解释:递归调用如下所示:
- [3,2,1,6,0,5] 中的最大值是 6 ,左边部分是 [3,2,1] ,右边部分是 [0,5] 。
    - [3,2,1] 中的最大值是 3 ,左边部分是 [] ,右边部分是 [2,1] 。
        - 空数组,无子节点。
        - [2,1] 中的最大值是 2 ,左边部分是 [] ,右边部分是 [1] 。
            - 空数组,无子节点。
            - 只有一个元素,所以子节点是一个值为 1 的节点。
    - [0,5] 中的最大值是 5 ,左边部分是 [0] ,右边部分是 [] 。
        - 只有一个元素,所以子节点是一个值为 0 的节点。
        - 空数组,无子节点。

示例 2:

输入:nums = [3,2,1]
输出:[3,null,2,null,1]

提示:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000
  • nums 中的所有整数 互不相同

思路:

这道题是用递归的方法,在这里,我们要进行相应的判断,我们要从数组中找出最大值,那么我们先设数组第一个元素为最大值,然后让他与数组后面的元素进行比较,得到最大值,把他用来作为根节点,后面就是递归,左节点是最大值左边的子数组,右节点是最大值右边的子数组,当左下标大于等于右下标,是递归结束的基线条件,结束返回答案。

解答:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* leveltravel(int* num,int start,int numsSize)
{
    if(start >= numsSize)
    {
        return NULL;
    }
    int max = num[start];
    int index = start;
    for(int i = start+1;i < numsSize;i++)
    {
        if(num[i] > max)
        {
            max = num[i];
            index = i;
        }
        else
        {
            max = max;
        }
    }
    struct TreeNode* node = malloc(sizeof(struct TreeNode));
    node->val = max;
    node->left = leveltravel(num,start,index);
    node->right = leveltravel(num,index+1,numsSize);
    return node;
}
struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize) {
    return leveltravel(nums,0,numsSize);
}

617.合并二叉树

给你两棵二叉树: root1root2

想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例 1:

输入:root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出:[3,4,5,5,4,null,7]

示例 2:

输入:root1 = [1], root2 = [1,2]
输出:[2,2]

提示:

  • 两棵树中的节点数目在范围 [0, 2000]
  • -104 <= Node.val <= 104

思路:

很简单的递归使用,但是要注意在递归时要用三元表达式来对元素进行判断,看它是否为空指针,其他的就是简单的判断,很快就能做出来。

解答:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* levelmerge(struct TreeNode* root1,struct TreeNode* root2)
{
    if(root1 == NULL && root2 == NULL)
    {
        return NULL;
    }
    struct TreeNode* node = malloc(sizeof(struct TreeNode));
    if(root1 != NULL && root2 != NULL)node->val = root1->val + root2->val;
    else if(root1 != NULL && root2 == NULL)node->val = root1->val;
    else if(root1 == NULL && root2 != NULL)node->val = root2->val;
    node->left = levelmerge(root1?root1->left:NULL,root2?root2->left:NULL);
    node->right = levelmerge(root1?root1->right:NULL,root2?root2->right:NULL);
    return node;
}
struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2) {
    return levelmerge(root1,root2);
}

700.二叉树搜索树中的搜索

给定二叉搜索树(BST)的根节点 root 和一个整数值 val

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 null

示例 1:

输入:root = [4,2,7,1,3], val = 2
输出:[2,1,3]

示例 2:

输入:root = [4,2,7,1,3], val = 5
输出:[]

提示:

  • 树中节点数在 [1, 5000] 范围内
  • 1 <= Node.val <= 107
  • root 是二叉搜索树
  • 1 <= val <= 107

思路:

当根节点的值与目标值相等时,我们会返回根节点,当根节点为空指针时,我们也会返回根节点。所以这是一个基线条件,同时这是一个二叉搜索树,左子节点小于根节点,根节点小于子右节点,所以当根节点大了时我们就选左节点,当根节点小了的话我们就选右节点。最终得到答案。

解答:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* searchBST(struct TreeNode* root, int val) {
    if(root == NULL || root->val == val)return root;
    struct TreeNode* node = NULL;
    if(root->val > val)node = searchBST(root->left,val);
    if(root->val < val)node = searchBST(root->right,val);
    return node;
}

98.验证二叉搜索树

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下:

  • 节点的左

    子树

    只包含

    小于

    当前节点的数。

  • 节点的右子树只包含 大于 当前节点的数。

  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:root = [2,1,3]
输出:true

示例 2:

输入:root = [5,1,4,null,null,3,6]
输出:false
解释:根节点的值是 5 ,但是右子节点的值是4。

提示:

  • 树中节点数目范围在[1, 104]
  • -2^31 <= Node.val <= 2^31 - 1

思路:

这里要注意对于每个节点,左子树中的所有节点值都小于该节点的值。右子树中的所有节点值都大于该节点的值。所以我们这里设置一个范围,在这个范围里,就是正确的,不在这个范围内就不对了,然后返回最终答案就行了。

解答:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool travellevel(struct TreeNode* root,long min,long max)
{
    if(root == NULL)
    {
        return true;
    }
    if(root->val <= min || root->val >= max)
    {
        return false;
    }
    return travellevel(root->left,min,root->val) && travellevel(root->right,root->val,max);
}
bool isValidBST(struct TreeNode* root) {
    return travellevel(root,LONG_MIN,LONG_MAX);
}

反思

今天的题并不难,最主要的还是每天坚持练习,到后面对于这些题都有了自己的思想,也就都能做了。

标签:node,TreeNode,struct,val,代码,随想录,第十七,root,节点
From: https://blog.csdn.net/2301_80630236/article/details/143427056

相关文章

  • Vue.js 混入(Mixins)高级用法:提升代码复用与灵活性
    在Vue.js中,混入(Mixins)是一种灵活的方式来分散可复用的代码。它们允许你将组件的选项分散到多个组件中,从而提升代码的复用性和灵活性。以下是一些混入的高级用法及示例。1.基础概念混入是一个包含Vue组件选项的对象,任何包含该混入的组件都可以使用这些选项。//定义......
  • 如何使用git将自己的代码上传到别人的gitee仓库
    1、git与gitee的关系1.Git是版本控制系统,它是一个本地工具,用于在开发者的计算机上跟踪和管理代码的历史记。2.Gitee是一个基于云的平台,类似于GitHub,它托管了数百万个Git存储库,开发者可以将他们的Git项目上传到Gitee以与其他人共享和协作。Gitee提供了一个可视化的界面和一......
  • 数据科学中的特征选择:方法、代码与实践
    在数据科学和机器学习领域,特征选择是一个至关重要的步骤,它涉及到从原始数据集中筛选出对模型预测能力有显著影响的特征。本文将详细介绍特征选择的几种主流方法,并提供相应的Python代码示例,以帮助读者在实际项目中应用这些技术。1.特征选择的重要性特征选择的目的是提高模......
  • PbootCMS模板调用友情链接标签代码
    适用范围:全站任意地方标签作用:用于依次输出指定分组的友情链接调用代码:html {pboot:linkgid=*num=*}<ahref="[link:link]"title="[link:name]"><imgsrc="[link:logo]"></a>{/pboot:link}控制参数:gid=*:分组,必填num=*:数量,非必填,默认为10个可使用的列表......
  • Dedecms批量提取第一张图片作为缩略图的代码
    <?php//获取文章内容functionbody($id){$sql="SELECTbodyFROMdede_archivesWHEREid='$id'";$result=mysql_query($sql);$row=mysql_fetch_assoc($result);return$row['body'];}//提取变量中第一个图片地址functio......
  • Java经典案例代码(持续更新中...)
    2024/11/3目录一、猜数小游戏二、求数组的最大值三、数组反转方法一:方法二:四、随机排名一、猜数小游戏importjava.util.Random;importjava.util.Scanner;publicclassrandom{publicstaticvoidmain(String[]args){Randomr=newRandom(......
  • 代码随想录算法训练营第十一天|leetcode150. 逆波兰表达式求值、leetcode239. 滑动窗
    1leetcode150.逆波兰表达式求值题目链接:150.逆波兰表达式求值-力扣(LeetCode)文章链接:代码随想录视频链接:栈的最后表演!|LeetCode:150.逆波兰表达式求值哔哩哔哩bilibili自己的思路:这是一道有思路,但是思路并不多的题目,就是我会觉得是先将数据进行添加,然后对于符号通过......
  • 代码随想录算法训练营第十五天|leetcode110. 平衡二叉树、leetcode257.二叉树的所有路
    1leetcode110.平衡二叉树题目链接:110.平衡二叉树-力扣(LeetCode)文章链接:代码随想录视频链接:后序遍历求高度,高度判断是否平衡|LeetCode:110.平衡二叉树_哔哩哔哩_bilibili1.1视频看后的思路1.1.1完整的代码就是不断判断,对其数据存储,其实突然发现每道题思路真的都很像,就......