算法妙妙屋-------1.递归的深邃回响:二叉树的奇妙剪枝

大佬们好呀,这一次讲解的是二叉树的深度搜索,大佬们请阅

1.前言

⼆叉树中的深搜(介绍)

深度优先遍历(DFS,全称为DepthFirstTraversal),是我们树或者图这样的数据结构中常⽤的⼀种***遍历算法***。这个算法会尽可能深的搜索树或者图的分⽀,直到⼀条路径上的所有节点都被遍历完毕,然后再回溯到上⼀层,继续找⼀条路遍历。
在⼆叉树中,常⻅的深度优先遍历为:前序遍历中序遍历以及后序遍历
因为树的定义本⾝就是递归定义,因此采⽤递归的⽅法去实现树的三种遍历不仅容易理解⽽且代码很简洁。并且前中后序三种遍历的唯⼀区别就是 ***访问根节点的时机不同***,在做题的时候,选择⼀个适当的遍历顺序,对于算法的理解是⾮常有帮助的。

好了,接下来让我们用习题来介绍吧

1.计算布尔⼆叉树的值(medium)

题目链接:计算布尔二叉树的值
题目介绍:

给你⼀棵完整⼆叉树的根,这棵树有以下特征:
叶⼦节点要么值为0要么值为1,其中0表⽰False,1表⽰True。
⾮叶⼦节点要么值为2要么值为3,其中2表⽰逻辑或OR,3表⽰逻辑与AND。
计算⼀个节点的值⽅式如下:
如果节点是个叶⼦节点,那么节点的值为它本⾝,即True或者False。
否则,计算两个孩⼦的节点值,然后将该节点的运算符对两个孩⼦值进⾏运算。
返回根节点root的布尔运算值。
完整⼆叉树是每个节点有0个或者2个孩⼦的⼆叉树。
叶⼦节点是没有孩⼦的节点。

在这里插入图片描述

算法思路:

    1. 对于规模为n的问题,需要求得当前节点值。
    1. 节点值不为0或1时, ***规模为n的问题可以被拆分为规模为n-1的⼦问题***:
  • a:所有⼦节点的值;
  • b:通过⼦节点的值运算出当前节点值。
    1. 当问题的规模变为n=1时,即叶⼦节点的值为0或1,我们可以直接获取当前节点值为0或1。

递归函数流程:

    1. 当前问题规模为n=1时,即叶⼦节点,直接返回当前节点值
    1. 递归求得左右⼦节点的值;
    1. 通过***判断当前节点的逻辑运算符***,计算左右⼦节点值运算得出的结果;

代码如下:

class Solution {
public:bool evaluateTree(TreeNode* root) {if(root->left==nullptr||root->right==nullptr){return root->val;}else{if(root->val==2)return evaluateTree(root->left)||evaluateTree(root->right);elsereturn evaluateTree(root->left)&&evaluateTree(root->right);}}
};

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

题目链接:求根节点到叶节点数字之和
题目介绍:
给你⼀个⼆叉树的根节点root,树中每个节点都存放有⼀个0到9之间的数字。
每条从根节点到叶节点的路径都代表⼀个数字:
例如,从根节点到叶节点的路径1->2->3表⽰数字123。
计算从根节点到叶节点⽣成的所有数字之和。
叶节点是指没有⼦节点的节点。

在这里插入图片描述
解题思路:

解法(dfs-前序遍历)

前序遍历按照根节点、左⼦树、右⼦树的顺序遍历⼆叉树的所有节点,通常⽤于 ⼦节点的状态依赖于⽗节点状态的题⽬

在前序遍历的过程中,我们可以 往左右⼦树传递信息,并且在回溯时得到左右⼦树的返回值。递归函数可以帮我们完成两件事:

  • 将⽗节点的数字与当前节点的信息整合到⼀起,计算出当前节点的数字,然后传递到下⼀层进⾏递归;
  • 当遇到叶⼦节点的时候,就***不再向下传递信息***,⽽是 ***将整合的结果向上⼀直回溯到根节点***。在递归结束时,根节点需要返回的值也就被更新为了整棵树的数字和。

递归函数流程:

    1. 当遇到空节点的时候,说明这条路从根节点开始没有分⽀,返回0
    1. 结合⽗节点传下的信息以及当前节点的val,计算出当前节点数字sum
    1. 如果当前结点是叶⼦节点,直接返回整合后的结果sum
    1. 如果当前结点不是叶⼦节点,将sum传到左右⼦树中去得到左右⼦树中节点路径的数字和,然后 ***相加后返回结果***。

代码如下:

class Solution {
public:int sumNumbers(TreeNode* root) {return sumNumber(root,0);}int sumNumber(TreeNode* root,int x) {if(root==nullptr)return x;else{x=x*10+root->val;}if(root->left!=nullptr&&root->right!=nullptr)return sumNumber(root->left,x)+sumNumber(root->right,x);else if(root->left!=nullptr)return sumNumber(root->left,x);else if(root->right!=nullptr)return sumNumber(root->right,x);elsereturn x;}
};

3.⼆叉树剪枝(medium)

题⽬链接:二叉树剪枝

题目介绍:

给你⼆叉树的根结点root,此外树的每个结点的值要么是0,要么是1。
返回移除了所有不包含1的⼦树的原⼆叉树。
节点node的⼦树为node本⾝加上所有node的后代。

在这里插入图片描述
解法(dfs-后序遍历):
后序遍历按照左⼦树、右⼦树、根节点的顺序遍历⼆叉树的所有节点,通常⽤于 ⽗节点的状态依赖于⼦节点状态的题⽬

后序遍历的主要流程:

    1. 递归出⼝:当传⼊节点为空时,不做任何处理;
    1. 递归处理***左⼦树***;
    1. 递归处理***右⼦树***;
    1. 处理当前节点:判断该节点是否为叶⼦节点(即左右⼦节点均被删除,前点成为叶⼦节点),并且节点的值为0
      a. 如果是,就删除掉;
      b. 如果不是,就不做任何处理

代码如下:

class Solution {
public:TreeNode* pruneTree(TreeNode* root) {dfs(root);if(root->left==nullptr&&root->right==nullptr&&root->val==0)return nullptr;elsereturn root;}bool dfs(TreeNode* root) {if (root) {if(root->left==nullptr&&root->right==nullptr)return root->val;bool l = dfs(root->left);bool r = dfs(root->right);if (l == false) {root->left = nullptr;}if (r == false) {root->right = nullptr;}if(root->val==0)return l || r;elsereturn 1;}elsereturn false;}
};

4. ⼆叉搜索树中第k⼩的元素(medium)

题目链接:⼆叉搜索树中第k⼩的元素

题目描述:
给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 小的元素(从 1 开始计数)。

在这里插入图片描述
解题思路:
(中序遍历+计数器剪枝)
上述解法不仅使⽤⼤量额外空间存储数据,并且会将所有的结点都遍历⼀遍。
但是,我们可以根据中序遍历的过程,只需扫描前k个结点即可。
因此,我们可以创建⼀个全局的计数器***count***,将其初始化为***k***,每遍历⼀个节点就将***count–***。直到某次递归的时候,count的值等于0,说明此时的结点就是我们要找的结果。

代码如下:

class Solution {
public:int kthSmallest(TreeNode* root, int k) {int flag = 0;dfs(root, k, flag);return flag;}void dfs(TreeNode* root, int& k, int& flag) {if (root) {dfs(root->left, k, flag);k--;if (k == 0) {flag = root->val;}dfs(root->right, k, flag);}}
};

好啦,递归问题就讲到这里,下一次讲解的是搜索,回溯和全排列,我们下次再见

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

深入解析DHCP带来了什么功能,服务器回应到底是用广播还是单播呢?

前言 不知道大家在看到这个图的时候第一时间想到的是什么,【好复杂】【看不懂】【终端数好多】,这里不看整体的结构怎么样,来看看终端数量都非常的多,终端要与网络中进行通信,势必需要IP地址,从最开始学习到…

<项目代码>YOLOv8 棉花识别<目标检测>

YOLOv8是一种单阶段(one-stage)检测算法,它将目标检测问题转化为一个回归问题,能够在一次前向传播过程中同时完成目标的分类和定位任务。相较于两阶段检测算法(如Faster R-CNN),YOLOv8具有更高的…

知乎日报前三周总结

目录 前言 首页 网络请求 上拉加载 详情页 加载WebView 左右滑动 主页与详情页同步更新 总结 前言 在这几周进行了知乎日报的仿写,这篇博客来总结一下前三周仿写的内容 首页 首页的界面如图所示,其实就是一个导航栏和一个数据视图组成的&#…

小白快速上手 labelimg:新手图像标注详解教程

前言 本教程主要面向初次使用 labelimg 的新手,详细介绍了如何在 Windows 上通过 Anaconda 创建和配置环境,并使用 labelimg 进行图像标注。 1. 准备工作 在开始本教程之前,确保已经安装了 Anaconda。可以参考我之前的教程了解 Anaconda 的…

【算法】【优选算法】二分查找算法(上)

目录 一、二分查找简介1.1 朴素二分模板1.2 查找区间左端点模版1.3 查找区间右端点模版 二、leetcode 704.⼆分查找2.1 二分查找2.2 暴力枚举 三、Leetcode 34.在排序数组中查找元素的第⼀个和最后⼀个位置3.1 二分查找3.2 暴力枚举 四、35.搜索插⼊位置4.1 二分查找4.2 暴力枚…

自己构建ARM平台DM8镜像

??? 为什么不使用官方提供的docker版本,测试有问题,分析函数不能使用,报错。 自己构建ARM平台的dm8镜像,参考 https://gitee.com/xlongfu/dm-docker/tree/master,发现一些问题 首先…

Linux之实战命令73:at应用实例(一百零七)

简介: CSDN博客专家、《Android系统多媒体进阶实战》一书作者 新书发布:《Android系统多媒体进阶实战》🚀 优质专栏: Audio工程师进阶系列【原创干货持续更新中……】🚀 优质专栏: 多媒体系统工程师系列【…

万字长文解读【深度学习面试——训练(DeepSpeed、Accelerate)、优化(蒸馏、剪枝、量化)、部署细节】

🌺历史文章列表🌺 深度学习——优化算法、激活函数、归一化、正则化深度学习——权重初始化、评估指标、梯度消失和梯度爆炸深度学习——前向传播与反向传播、神经网络(前馈神经网络与反馈神经网络)、常见算法概要汇总万字长文解读…

C++ | Leetcode C++题解之第554题砖墙

题目&#xff1a; 题解&#xff1a; class Solution { public:int leastBricks(vector<vector<int>>& wall) {unordered_map<int, int> cnt;for (auto& widths : wall) {int n widths.size();int sum 0;for (int i 0; i < n - 1; i) {sum wi…

DDei在线设计器V1.2.42版发布

V1.2.42版 新特性&#xff1a; 1.快捷编辑框可以映射到主控件的多个属性上&#xff0c;从而实现快速编辑。 2.跟随图形的支持范围增加&#xff0c;从仅支持线控件到支持所有控件 2.新增控件双击回调函数EVENT_CONTROL_DBL_CLICK&#xff0c;可以用于覆盖默认的快速编辑逻辑…

大数据的实时处理:工具和最佳实践

在当今的数字世界中&#xff0c;数据以前所未有的速度从无数来源生成&#xff0c;包括社交媒体、物联网设备、电子商务平台等。随着组织认识到这些数据的潜在价值&#xff0c;他们越来越多地转向实时处理&#xff0c;以获得即时、可操作的见解。但是&#xff0c;实时处理大数据…

【51单片机】蜂鸣器演奏音乐——小星星天空之城

学习使用的开发板&#xff1a;STC89C52RC/LE52RC 编程软件&#xff1a;Keil5 烧录软件&#xff1a;stc-isp 开发板实图&#xff1a; 文章目录 蜂鸣器按键发声无源蜂鸣器演奏音乐简单乐理小星星天空之城 蜂鸣器 蜂鸣器在开发板的位置如下&#xff1a; 蜂鸣器是一种将电信号转…

【含开题报告+文档+源码】高校校园二手交易平台的设计与实现

开题报告 随着互联网的快速发展&#xff0c;电子商务成为了现代化社会中不可或缺的一部分。线上交易平台的兴起&#xff0c;为商家和消费者创造了更多的交易机会和便利。然而&#xff0c;传统的电商平台通常由一家中央机构管理和控制&#xff0c;对商家和消费者的自由度有一定…

录制的音频听起来非常缓慢,声音很模糊

一、主题 录制的音频听起来非常缓慢&#xff0c;声音很模糊 二、问题背景 硬件&#xff1a;T113&#xff0c;R528等平台系列产品 软件&#xff1a;Tina5.0 三、问题描述 1、复现步骤 使用arecord进行录音。 arecord -Dhw:audiocodec -f S16_LE -r 16000 -c 2 -d 5 /tmp/t…

计算机的错误计算(一百五十)

摘要 探讨 MATLAB 中 的计算精度问题。当 为含有小数的大数或 &#xff08;&#xff09;附近数时&#xff0c;输出会有错误数字。 例1. 已知 计算 直接贴图吧&#xff1a; 另外&#xff0c;16位的正确值分别为 -0.7882256119904400e0、0.1702266977524110e0、-0.…

【网络安全 | 漏洞挖掘】Google SSO用户的帐户接管

未经许可,不得转载。 文章目录 DOM XSS获取 CSRF Token解除Google账户绑定在这篇博文中,我将详细介绍找到针对Google SSO用户的账号接管(ATO)漏洞的过程。 DOM XSS 我遇到 DOM XSS 漏洞的位置非常微妙,因为我遇到了非常严格的WAF。 获取 CSRF Token 在找到XSS漏洞后,我…

2024中国游戏出海情况

01 哪里出海更花钱&#xff1f; 报告显示&#xff0c;中国手游在全球不同市场的获客成本不同&#xff0c;整体来看北美市场竞争更加激烈&#xff0c;其安卓和iOS获客成本是拉丁美洲的12倍和7倍。 按具体市场划分&#xff0c;获客成本最高的TOP 3为韩国、美国和日本&#xff0c…

AI写作(七)的核心技术探秘:情感分析与观点挖掘

一、AI 写作中的关键技术概述 情感分析与观点挖掘在 AI 写作中起着至关重要的作用。情感分析能够帮助 AI 理解文本中的情感倾向&#xff0c;无论是正面、负面还是中性。在当今信息时代&#xff0c;准确把握用户情绪对于提供个性化体验和做出明智决策至关重要。例如&#xff0c;…

AlphaProof IMO 2024 P1 in LEAN 之 简介

AlphaProof 是用于进行数学证明的人工智能&#xff0c;其中&#xff0c;对于 IMO 2024 中的6道题中的 4 道。本系列博文&#xff0c;就 AlphaProof 对于 IMO 2024 P1 给出的答案进行详细讲述。这里是此系列的第一篇。 IMO 2024 P1 题目如下&#xff1a; IMO 2024 P1 答案 α 为…