算法系列--递归(2)

💕"什么样的灵魂就要什么样的养料,越悲怆的时候我越想嬉皮。"💕
作者:Mylvzi
文章主要内容:算法系列–递归(2)
在这里插入图片描述

前言:今天带来的是算法系列--递归(2)的讲解,包含六个和二叉树相关的题目哦

1.计算布尔⼆叉树的值

链接: https://leetcode.cn/problems/evaluate-boolean-binary-tree/
在这里插入图片描述

分析:

  1. 函数头:传入节点,得到左右子树的值, boolean dfs(TreeNode root)
  2. 函数体:dfs(root.left); dfs(root.right)
  3. 递归出口:当遇到叶子结点的时候直接返回即可

代码:

class Solution {
    public boolean evaluateTree(TreeNode root) {// 函数头就是这样
        if(root.left == null) return root.val == 0 ? false : true;

        boolean left = evaluateTree(root.left);// 得到左子树的值
        boolean right = evaluateTree(root.right);// 得到右子树的值

        return root.val == 2 ? left | right : left & right;// 判断
    }
}

2.求根节点到叶节点数字之和

链接: https://leetcode.cn/problems/sum-root-to-leaf-numbers/
在这里插入图片描述

分析:
在这里插入图片描述

代码:

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root,0);
    }

    private int dfs(TreeNode root, int presum) {
        // 1.计算当前节点的值
        presum = presum * 10 + root.val;

        // 递归出口
        if(root.left == null && root.right == null) return presum;

        // 2.递归左子树
        int ret = 0;
        if(root.left != null) ret += dfs(root.left,presum);

        // 3.递归右子树
        if(root.right != null) ret += dfs(root.right,presum);

        // 4.返回左右子树的总和
        return ret;
    }
}

总结:
当一个递归函数不好想时,就去模拟一遍整个过程

比如本题,你要想想这个接口是干啥的,你想要这个接口帮你做什么–给接口一个根节点,你去给我算出左右子树的和,并且返回给我,那么就能确定出函数头;

  • 返回值:int类型,左子树 + 右子树的和
  • 函数名:dfs
  • 参数:root,还要给我走到当前节点的值,我只有知道这个值,才能和子节点相连

3.⼆叉树剪枝

链接: https://leetcode.cn/problems/binary-tree-pruning/description/

在这里插入图片描述

分析:

  • 明确接口的作用:给你一个根节点root,你去给我判断左右子树是否满足剪枝的条件,如果满足就断开和根节点的连接,如果不满足继续保持连接即可
  • 函数头:返回值应该是TreeNode,当条件满足时,需要断开连接,直接返回null就可以实现,如果条件不满足,还是需要返回子根节点;函数名dfs,参数需要通过一个根节点就行
  • 函数体:先分别遍历左右子树,更新root的左右子树的连接条件,接着判断是否满足剪枝的条件,如果满足,返回null,表示需要剪枝,如果不满足,返回当前的根节点即可
  • 递归出口:当节点为空时,直接返回null

代码:

class Solution {
    public TreeNode pruneTree(TreeNode root) {
        return dfs(root);
    }

    private TreeNode dfs(TreeNode root) {
        if(root == null) return null;// 递归出口

        root.left = dfs(root.left);// 遍历左子树
        root.right = dfs(root.right);// 遍历右子树

        if(root.left == null && root.right == null && root.val == 0) // 条件满足将root置为空
            return null;
        else return root;
    }
}

4. 验证⼆叉搜索树

链接: https://leetcode.cn/problems/validate-binary-search-tree/description/
在这里插入图片描述

分析:

本题要利用到二叉搜索树的一个性质–二叉搜索树的中序遍历的结果是一个有序序列

  • 明确接口的作用:给你一个根节点,你去给我判断一下左右子树是否都符合二叉搜索树的条件,如果不满足直接返回false,满足返回true
  • 函数头:返回值是boolean,参数需要提供一个根节点,函数名是dfs
  • 函数体:由于要中序遍历,所以应该先遍历左子树,判断左子树是否满足二叉搜索树,如果不满足,直接返回false即可(此时就没有遍历根节点和右子树的必要了),如果满足,判断当前根节点的状态是否满足二叉搜索树,具体的判断条件就是比较root.val和prev值的大小,如果root.val < prev,则不符合二叉搜索树的条件,直接返回false,如果root.val > prev,则符合二叉搜索树的条件,继续判断右子树是否符合条件,如果右子树满足,返回true,如果不满足,返回false
  • 递归出口:当节点为空时,返回true

在这里插入图片描述

代码:

class Solution {
    // 二叉搜索树的性质:中序遍历的结果是一个有序的序列
    long prev = Long.MIN_VALUE;// 设置为long是为了防止越界

    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;// 空树也是二叉搜索树

        boolean left = isValidBST(root.left);
        if(left == false) return false;// 剪枝

        boolean cur = root.val > prev ? true : false;
        if(cur == false) return false;// 剪枝
        prev = root.val;// 更新prev

        boolean right = isValidBST(root.right);

        return right;
    }
}

5.⼆叉搜索树中第 k ⼩的元素

链接: https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/
在这里插入图片描述

分析:

本题还是利用二叉搜索树的性质:二叉搜索树的中序遍历的结果是一个有序序列

设计一个ret作为返回值,设计一个cnt计数器,让cnt的初始值为k,通过中序遍历,每遍历到一个节点就让cnt--,当cnt = 0是,将ret更新为cur.val,然后返回即可

代码:

class Solution {
    int cnt;
    int ret;
    public int kthSmallest(TreeNode root, int k) {
        cnt = k;
        dfs(root);
        return ret;
    }

    private void dfs(TreeNode root) {
        if(root == null || cnt == 0) return;

        dfs(root.left);
        cnt--;
        if(cnt == 0) ret = root.val;
        dfs(root.right);
    }
}

6.⼆叉树的所有路径

链接: https://leetcode.cn/problems/binary-tree-paths/

在这里插入图片描述

分析:

  • 明确接口的作用:给你一个根节点,给我拼接上左子树和右子树

  • 函数头: 需要提供一个根节点和走到当前节点之前已经拼接好的字符串(path)

  • 函数体:先创建出一个新的字符串用于接受path,接着以这个新的字符串为基准,遍历左子树和右子树

  • 递归出口:当root为叶子节点时,证明一个完整的二叉树路径已经被拼接完毕,让ret添加这个拼接完毕的字符串路径即可

代码:

class Solution {
    List<String> ret = new ArrayList<>();// 返回值
    
    public List<String> binaryTreePaths(TreeNode root) {
        dfs(root,new StringBuffer());
        return ret;
    }

    private void dfs(TreeNode root,StringBuffer path) {
        StringBuffer newPath = new StringBuffer(path);
        newPath.append(Integer.toString(root.val));
        if(root.left == null && root.right == null) {
            ret.add(newPath.toString());
            return;
        }

        newPath.append("->");
        if(root.left != null) dfs(root.left,newPath);
        if(root.right != null) dfs(root.right,newPath);
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/481598.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

企业微信可以更换公司主体吗?

企业微信变更主体有什么作用&#xff1f;当我们的企业因为各种原因需要注销或已经注销&#xff0c;或者运营变更等情况&#xff0c;企业微信无法继续使用原主体继续使用时&#xff0c;可以申请企业主体变更&#xff0c;变更为新的主体。企业微信变更主体的条件有哪些&#xff1…

Ambari+Metrics+Bigtop 全家桶编译部署攻略——Ambari系列

您的支持是我继续创作与分享的动力源泉!!! 您的支持是我继续创作与分享的动力源泉!!! 您的支持是我继续创作与分享的动力源泉!!! 写在前面: 1、源码已经完成Ambari+Metrics+Bigtop 最新版的编译及部署,后续会放魔改包和一件部署脚本 2、时间有限,我会尽快更新完毕所有内容…

python 空间距离计算

目录 python 空间距离计算 已知两点&#xff0c;画三角形 批量矩阵计算 python 空间距离计算 要在空间中找到一个点&#xff0c;使其位于点 b 和 c 之间的连线上&#xff0c;并且与点 b 的距离等于点 a 到点 b 的距离的2倍。 import numpy as npif __name__ __main__:a …

【机器学习入门 】逻辑斯蒂回归和分类

系列文章目录 第1章 专家系统 第2章 决策树 第3章 神经元和感知机 识别手写数字——感知机 第4章 线性回归 文章目录 系列文章目录前言一、分类问题的数学形式二、最大似然估计三、交叉熵损失函数四、多类别分类多类别逻辑斯蒂回归归一化指数函数交叉熵误差和均方误差的比较 五…

docker (一)

1&#xff0c;什么是docker 首先我们可以好好的看看docker的那个可能的图标&#xff0c;你想象到了什么&#xff1f; ... docker是一个开源的应用容器引擎&#xff0c;有Docker公司&#xff08;前dotCloud公司&#xff09;开发&#xff0c;基于Apache2.0开源授权协议发行。该…

网络工程师笔记15(OSPF协议-2)

OSPF协议 OSPF是典型的链路状态路由协议&#xff0c;是目前业内使用非常广泛的 IGP 协议之一。 Router-ID(Router ldentifier&#xff0c;路由器标识符)&#xff0c;用于在一个 OSPF 域中唯一地标识一台路由器。Router-ID 的设定可以通过手工配置的方式&#xff0c;或使用系统自…

吴恩达机器学习笔记 二十七 决策树中连续值特征的选择 回归树

还是猫狗分类的案例&#xff0c;假如再增加一个特征weight&#xff0c;该值是一个连续的值&#xff0c;如何在决策树中使用该特征&#xff1f; 如下图所示&#xff0c;尝试不同的阈值&#xff0c;如 weight<9 , 此时左边有四个样本&#xff0c;都为猫&#xff0c;右边有六个…

c语言--内存函数的使用(memcpy、memcmp、memset、memmove)

目录 一、memcpy()1.1声明1.2参数1.3返回值1.4memcpy的使用1.5memcpy模拟使用1.6注意 二、memmove()2.1声明2.2参数2.3返回值2.4使用2.5memmove&#xff08;&#xff09;模拟实现 三、memset3.1声明3.2参数3.3返回值3.4使用 四、memcmp()4.1声明4.2参数4.3返回值4.4使用 五、注…

Android视角看鸿蒙第八课(module.json5中的各字段含义之abilities)下

Android视角看鸿蒙第八课(module.json5中的各字段含义之abilities&#xff09;下 导读 上篇文章开始学习abilities下的各字段含义&#xff0c;因为篇幅原因只学习了name、srcEntry、description、icon和label字段的含义和用法&#xff0c; 这篇文章继续学习和了解其他字段。 …

二叉树|106.从中序与后序遍历序列构造二叉树

力扣题目链接 class Solution { private:TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {if (postorder.size() 0) return NULL;// 后序遍历数组最后一个元素&#xff0c;就是当前的中间节点int rootValue postorder[postorder.…

二分查找法总结

目录 1、思路讲解&#xff08;LC704&#xff09;2、代码思路讲解&#xff08;循环不变量&#xff09;&#xff08;1&#xff09; 左闭右闭&#xff08;2&#xff09;左闭右开&#xff08;3&#xff09;总结&#xff1a;左开右闭和左闭右开&#xff08;4&#xff09;复杂度分析 …

TCP和UDP 传输层协议的区别

TCP协议 当一台计算机想要与另一台计算机通讯时&#xff0c;两台计算机之间的通信需要畅通且可靠&#xff0c;这样才能保证正确收发数据。例如&#xff0c;当你想查看网页或查看电子邮件时&#xff0c;希望完整且按顺序查看网页&#xff0c;而不丢失任何内容。当你下载文件时&…

Docker学习笔记 - 基本概念

一. 什么是“容器”&#xff08;container&#xff09;和“镜像”&#xff08;Image&#xff09; 所谓“容器”可以理解为一个模拟操作系统的虚拟层&#xff0c;大部分是基于Linux的&#xff0c;应用程序及其配置信息&#xff0c;依赖库可以打包成一个Image独立运行在这个虚拟…

nvidia显卡如何安装cuda驱动

目录 查看显卡对应的cuda版本下载与你显卡匹配的CUDA Toolkit 查看显卡对应的cuda版本 按 微软 R 键&#xff0c;输入cmd 然后输入 nvidia-smi &#xff0c;回车显示下面信息&#xff1a; 看到 CUDA Version 为 12.2 下载与你显卡匹配的CUDA Toolkit 打开网页&#xff1a…

【竞技宝】DOTA2:梦幻联赛预spirit惨遭淹死 LGD不敌KEV

北京时间2024年3月23日,近期各大赛区的一线战队参加的比赛暂时告一段落,目前关注度最高的比赛是正在进行的梦幻联赛S23预选赛,本以为各大战队能够在实力差距明显的预选赛中轻松突围,没想到本次预选赛目前为止却是冷门频出。 近日,梦幻联赛S23的东欧区预选赛已经全部结束,最终NA…

C语言----动态内存

学到这里了&#xff0c;大家应该对C语言的了解跟深一层了吧。我们C语言写代码不能只局限于直接写代码。我们要了解C语言的内存分布&#xff0c;我们都知道C语言的内存是有堆区&#xff0c;栈区&#xff0c;静态区的。然后栈区是我们平常创建临时变量存储的地方&#xff0c;静态…

3.23项目:聊天室

1、 基于UDP的网络聊天室 项目需求&#xff1a; 如果有用户登录&#xff0c;其他用户可以收到这个人的登录信息如果有人发送信息&#xff0c;其他用户可以收到这个人的群聊信息如果有人下线&#xff0c;其他用户可以收到这个人的下线信息服务器可以发送系统信息 服务器 #inc…

四年蓄势,TikTok决定硬刚

在X平台&#xff08;原推特&#xff09;上线的一则视频里&#xff0c;周受资看起来又焦急&#xff0c;又强硬。他的眉毛扭到了一起&#xff0c;完全不像去年那个在美国国会听证会上&#xff0c;接受了5小时高压问询&#xff0c;仍风度翩翩的跨国公司CEO。 “过去几年来&#x…

js数据流详细讲解

文章目录 单向数据流单向数据流示例: 双向数据流双向数据流示例: 延伸和扩展状态管理Redux 示例&#xff1a; 异步数据流异步操作示例&#xff08;使用 async/await&#xff09;&#xff1a; 数据转换和处理数据处理示例&#xff08;使用 lodash&#xff09;&#xff1a; 实时数…

解决大型多模态模型的幻觉问题,新方法AITuning助力AI更可靠

引言&#xff1a;多模态对话幻觉的挑战 在人工智能领域&#xff0c;开发能够通过视觉和语言等多种渠道与人类互动的通用助手是一个重要问题。受到大型语言模型&#xff08;LLMs&#xff09;如ChatGPT的显著成功的启发&#xff0c;研究社区对开发能够支持视觉-语言指令的多模态助…