【Leetcode每日一题】 递归 - 二叉树剪枝(难度⭐⭐)(50)

1. 题目解析

题目链接:814. 二叉树剪枝

这个问题的理解其实相当简单,只需看一下示例,基本就能明白其含义了。

2.算法原理

想象一下,你有一堆层层叠叠的积木,你想从底部开始,把那些标记为0的积木拿走。如果直接从上面开始拿,你可能会碰到很多麻烦,因为你不知道下面的积木长什么样,也不敢轻易动它们。但是,如果你从最下面的积木开始,一层一层往上拿,事情就变得简单多了。

这就像我们处理二叉树一样。如果从上往下删除节点,我们就需要知道左右子树的情况,这确实是个头疼的问题。但反过来,如果我们从下往上,也就是从最底层的叶子节点开始,删除那些值为0的叶子节点,然后再处理上一层,这样问题就简单多了。

具体来说,我们可以采用后序遍历的方法。后序遍历就是先处理左子树,再处理右子树,最后处理当前节点。当我们处理到当前节点时,只要判断它是不是叶子节点,并且值是不是0,如果是的话,就直接删除它。

不过要注意,当我们删除一个叶子节点后,它的父节点可能就变成新的叶子节点了。所以,处理完当前节点后,我们还需要检查它的父节点是否需要处理。这就是为什么我们选择后序遍历的原因,因为后序遍历最先遍历到的总是叶子节点。

算法流程可以这样描述:

  1. 定义一个递归函数dfs(TreeNode*& root),这个函数会检查当前节点是否需要删除。

  2. 递归的出口:如果传入的节点为空,那么直接返回,不需要做任何处理。

  3. 递归处理左右子树:先调用dfs函数处理左子树,再处理右子树。

  4. 处理当前节点

    • 判断当前节点是否已经是叶子节点(即左右子节点都被删除了),并且节点的值为0。
    • 如果是的话,就删除这个节点。
    • 如果不是,就保持原样,不做任何处理。

通过这样的方式,我们可以从底部开始,逐步删除值为0的叶子节点,并且保证删除后的树仍然满足我们的要求。当所有的叶子节点都被检查并处理完毕后,如果它们的值都是1,那就说明整棵树都包含1,此时我们就可以返回结果了。

这种方法的好处是,它让删除操作变得相对简单,而且不会影响最终的结果。就像我们一层一层地拿走积木,最后留下的都是我们想要的。

3.代码编写

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution 
{
public:
    TreeNode* pruneTree(TreeNode* root) 
    {
        if(root == nullptr) return nullptr;
        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);
        if(root->left == nullptr && root->right == nullptr && root->val == 0)
        {
            delete root;
            root = nullptr;
        }
        return root;
    }
};

The Last

嗯,就是这样啦,文章到这里就结束啦,真心感谢你花时间来读。

觉得有点收获的话,不妨给我点个吧!

如果发现文章有啥漏洞或错误的地方,欢迎私信我或者在评论里提醒一声~ 

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

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

相关文章

设计模式之观察者模式讲解

概念:定义对象间一种一对多的依赖关系,使得当每一个对象改变状态,则所有依赖于它的对象都会得到通知并被自动更新。 抽象主题:或者叫被观察者,可以持有、增加、删除观察者对象。具体主题:实现抽象主题定义的…

定时任务原理方案综述

定时任务原理方案综述 背景概述 定时任务,顾名思义,就是指定时间点进行执行相应的任务。业务场景中包括: 每天晚上12点,将当日的销售数据发送给各个VP;订单下单十分钟未付款将自动取消订单;用户下单后发…

【JavaScript】预解析 ② ( 预解析示例分析 | 分步骤分析预解析过程 )

文章目录 一、预解析示例分析一1、要分析的代码2、代码预解析分析3、作用域链分析 二、预解析示例分析二1、要分析的代码2、代码预解析分析 三、预解析示例分析三1、要分析的代码2、预解析过程分析 一、预解析示例分析一 1、要分析的代码 要分析的 代码示例 : <!DOCTYPE ht…

人工智能前沿成科技竞争新高地

以下文章来源&#xff1a;经济参考报 近日&#xff0c;首届中国具身智能大会&#xff08;CEAI 2024&#xff09;在上海举行。作为人工智能领域的前沿热点&#xff0c;具身智能正逐步走进现实&#xff0c;成为当前全球科技竞争的新高地、未来产业的新赛道、经济发展的新引擎。 “…

人工智能_大模型018_AssistantsAPI_01_---人工智能工作笔记0154

先来说一下一些问题: 尽量不要微调,很麻烦,而且效果需要自己不断的去测试. 如果文档中有图表,大量的图片去分析就不合适了. 是否用RAG搜索,这个可以这样来弄,首先去es库去搜能直接找到答案可以就不用去RAG检索了,也可以设置一个分,如果低于60分,那么就可以去进行RAG检索 微…

视频实例分割 | 基于ViT实现的端到端end-to-end+query-based的视频实例分割

项目应用场景 面向视频实例分割场景&#xff0c;项目采用 Vision-Transformer 深度学习算法来实现。 项目效果 项目细节 > 具体参见项目 README.md (1) 创建 python 开发环境 conda create --name tevit python3.7.7 conda activate tevit (2) 安装依赖 torch1.9.0 torch…

XC7A35T-2FGG484 嵌入式FPGA现场可编程门阵列 Xilinx

XC7A35T-2FGG484 是一款由Xilinx&#xff08;赛灵思&#xff09;制造的FPGA&#xff08;现场可编程门阵列&#xff09;芯片 以下是XC7A35T-2FGG484 的主要参数&#xff1a; 1. 系列&#xff1a;Artix-7 2. 逻辑单元数量&#xff1a;33280个 3. 工艺技术&#xff1a;28nm 4. …

postgresql发布和订阅

一、发布订阅介绍 发布和订阅使用了pg的逻辑复制的功能&#xff0c;通过发布端创建publication与表绑定&#xff0c;订阅端创建subscription同时会在发布端创建逻辑复制槽实现逻辑复制功能 逻辑复制基于 发布&#xff08;Publication&#xff09; 与 订阅&#xff08;Subscri…

Few-Shot目标检测数据集 | Few-Shot目标检测数据集_已经整理成MS-COCO数据格式_含60000+张图_可直接用于目标检测算法训练

项目应用场景 面向 Few-Shot 目标检测场景&#xff0c;项目提供 6000 张图&#xff0c;已经整理成 MS-COCO 数据格式&#xff0c;可用于 Few-Shot 目标检测的训练数据集&#xff0c;或作为 Few-Shot 目标检测数据集的补充。 数据集展示 数据集下载 > 具体参见项目 README.m…

FreeBuf 全球网络安全产业投融资观察(3月)

综述 据不完全统计&#xff0c;2024年3月&#xff0c;全球网络安全市场共发生投融资事件53起&#xff0c;其中国内4起&#xff0c;国外49起。 3月全球络安全产业投融资统计表&#xff08;数据来源&#xff1a;航行资本、36氪&#xff09; 整体而言&#xff0c;国内4起投融资事…

数字图像处理基础

目录 概述 仿射变换 常见的灰度处理算法 空间域滤波原理 空间域平滑滤波&#xff08;低通滤波&#xff09; 空间域锐化滤波&#xff08;高通滤波&#xff09; 傅里叶变换 频率域与空间域的对应关系 频率域滤波 形态学处理基础知识 边缘检测原理 检测孤立点 检测线…

软考之零碎片段记录(九)+复习巩固(四)

一、学习 1. 英语单词 delivery:交付 automation:自动化 build-in:内置 Iwell-konwn:众所周知 modern:现代 hands-off:无干预 labor-free:免人工 visual:可视化 object-oriented:面向对象的 structural:结构化的 2. 案例 E1: 租户信息 E2: 农户 E3: 租户 E4: 用户 3. 案例…

giteegit的连结使用

目标&#xff1a;在windows的本地的git上操作的项目存放到Gitee云端上 不适用于linux的terminal终端下 1.先下载好Git这个软件 2.创建一个文件夹&#xff08;项目名称&#xff09; 然后用gitbash的形式打开 3.创建ssh密钥到Gitee上 因为我们在Git与Gitee上的传输是通过ssh…

OpenCV图像处理——基于OpenCV的ORB算法实现目标追踪

概述 ORB&#xff08;Oriented FAST and Rotated BRIEF&#xff09;算法是高效的关键点检测和描述方法。它结合了FAST&#xff08;Features from Accelerated Segment Test&#xff09;算法的快速关键点检测能力和BRIEF&#xff08;Binary Robust Independent Elementary Feat…

Golang | Leetcode Golang题解之第17题电话号码的字母组合

题目&#xff1a; 题解&#xff1a; var phoneMap map[string]string map[string]string{"2": "abc","3": "def","4": "ghi","5": "jkl","6": "mno","7": &…

数据处理|dataframe的连接操作merge

pd.merge() pd.merge(left, right, howinner, onNone, left_onNone, right_onNone,left_indexFalse, right_indexFalse, sortTrue,suffixes(_x, _y), copyTrue, indicatorFalse,validateNone)merge内部的各种参数 pd.left,pd.right left用来指代左边要拼接的dataframe right…

RocketMQ 之 IoT 消息解析:物联网需要什么样的消息技术?

作者&#xff1a;林清山&#xff08;隆基&#xff09; 前言&#xff1a; 从初代开源消息队列崛起&#xff0c;到 PC 互联网、移动互联网爆发式发展&#xff0c;再到如今 IoT、云计算、云原生引领了新的技术趋势&#xff0c;消息中间件的发展已经走过了 30 多个年头。 目前&a…

【论文阅读——Profit Allocation for Federated Learning】

1.摘要 由于更为严格的数据管理法规&#xff0c;如《通用数据保护条例》&#xff08;GDPR&#xff09;&#xff0c;传统的机器学习服务生产模式正在转向联邦学习这一范式。联邦学习允许多个数据提供者在其本地保留数据的同时&#xff0c;协作训练一个共享模型。推动联邦学习实…

知识管理系统|基于Springboot和vue的知识管理系统设计与实现(源码+数据库+文档)

知识管理 目录 基于Springboot和vue的知识管理系统设计与实现 一、前言 二、系统设计 三、系统功能设计 1、前台&#xff1a; 5.2.2 文章信息 5.3.1 论坛交流 2、后台 用户管理 5.1.2 文章分类 5.2.1 资料分类 四、数据库设计 五、核心代码 六、论文参考 七、最…

【面经】2023年软件测试面试题大全(持续更新)附答案

前阵子一位读者告诉我&#xff0c;某位大厂HR给他发了我之前做的面试题答案合集。 这个消息让我开心了一整天&#x1f602;&#xff0c;因为这说明我之前做的面试题系列真的能帮助到部分测试同学&#xff0c;也算是侧面得到了一种认可吧。 坚持可是我们程序员家族的优良传统&a…