首页 > 其他分享 >力扣---1080. 根到叶路径上的不足节点

力扣---1080. 根到叶路径上的不足节点

时间:2023-05-22 18:55:20浏览次数:41  
标签:力扣 路径 1080 符合要求 --- limit null root 节点

给你二叉树的根节点 root 和一个整数 limit ,请你同时删除树中所有 不足节点 ,并返回最终二叉树的根节点。

假如通过节点 node 的每种可能的 “根-叶” 路径上值的总和全都小于给定的 limit,则该节点被称之为 不足节点 ,需要被删除。

叶子节点,就是没有子节点的节点。

 

示例 1:

输入:root = [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14], limit = 1
输出:[1,2,3,4,null,null,7,8,9,null,14]
示例 2:

输入:root = [5,4,8,11,null,17,4,7,1,null,null,5,3], limit = 22
输出:[5,4,8,11,null,17,4,7,null,null,null,5]
示例 3:

输入:root = [1,2,-3,-5,null,4,null], limit = -1
输出:[1,null,-3,4]
 

提示:

树中节点数目在范围 [1, 5000] 内
-105 <= Node.val <= 105
-109 <= limit <= 109

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/insufficient-nodes-in-root-to-leaf-paths
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


 

题目是真的绕。写了三次代码再加上直接看答案才反应过来题目是要干啥。

1. 不符合要求的节点要删掉。

2. 是否符合要求是按照叶节点来判断,而不是将某个节点作为叶节点来判断。

3. 空节点直接是不符合要求。

class Solution {
    public TreeNode sufficientSubset(TreeNode root, int limit) {
        if (dfs(root, limit, 0)) {
            return root;
        } else {
            return null;
        }
    }
    private boolean dfs (TreeNode root, int limit, int sum) {
        if (root == null) {
            return false;
        }
        sum += root.val;
        // 遇到叶节点后,判断这条路径是否符合要求。
        if (root.left == null && root.right == null) {
            return sum >= limit;
        }
        boolean juLeft = dfs(root.left, limit, sum);
        // 如果左边的路径不符合要求,则需要删掉。
        if (!juLeft) {
            root.left = null;
        }
        boolean juRight = dfs(root.right, limit, sum);
        // 如果右边的路径不符合要求,则需要删掉。
        if (!juRight) {
            root.right = null;
        }
        // 返回包含该节点的路径是否符合要求(而不是返回以该节点为叶节点的路径是否符合要求。)
        return  juLeft || juRight;
    }
}

 

标签:力扣,路径,1080,符合要求,---,limit,null,root,节点
From: https://www.cnblogs.com/allWu/p/17421461.html

相关文章

  • java基于joda-date实现获取两个时间段对应类型的所有时间,比如说两年之间的所有日期,两
    /***获取两个时间段对应类型的所有时间**@paramtype日期类型,包含day、month、year*@parambeginTime开始时间*@paramendTime结束时间*@return*/publicstaticList<String>getBetweenTime(Stringtype,String......
  • 领域驱动设计-软件核心复杂性应对之道:第七章
    第七章使用语言:一个扩展的实例7.1货物运输系统简介1)跟踪客户货物的主要处理部署2)事先预约货物3)当货物到达其处理过程中的某个位置时,自动向客户寄送发票一个货物从货主手上通过托运公司运输货物,从起始点到目的地,托运公司(可能只负责一段路途,再由合作伙伴/外包/私人等接力)负......
  • 经纬恒润新产品系列 | 这款AR-HUD将颠覆你的认知
        随着科技的发展与突破,智能化产品在汽车领域扮演了越来越重要的角色。本文即将介绍经纬恒润新产品——AR-HUD(增强现实抬头显示系统),它可以将科幻电影中的驾驶场景变为现实——将信息投影在挡风玻璃上,基于此功能,AR-HUD还可以标记路况、天气、温度等信息,这将极大地提高驾驶......
  • Codeforces Gym 103119B - Boring Problem(高斯消元)
    考虑建出AC自动机,朴素做法是高斯消元,\(f_i=\sum\limits_{j=0}^{k-1}f_{to_{i,j}}p_j+1\),复杂度\(O(n^3m^3)\),不能接受。考虑优化高斯消元的过程,我们定义以下节点为“关键点”:根节点对于一个trie树(也就是未经过AC自动机getfail操作得到的树)上有超过两个儿子的节点\(x......
  • VMware ESXi 6.0 U3 Final - ESXi 6 系列最终版下载
    VMwareESXi6.0U3Final-ESXi6系列最终版下载VMwareESXi6Standard请访问原文链接:https://sysin.org/blog/vmware-esxi-6/,查看最新版。原创作品,转载请保留出处。作者主页:sysin.orgVersionReleaseNameReleaseDateBuildNumberInstallerBuildNumberAvailab......
  • VMware ESXi 6.5 U3 Final - ESXi 6 系列最终版下载
    VMwareESXi6.5U3Final-ESXi6系列最终版下载VMwareESXi6Standard请访问原文链接:https://sysin.org/blog/vmware-esxi-6/,查看最新版。原创作品,转载请保留出处。作者主页:sysin.orgVersionReleaseNameReleaseDateBuildNumberInstallerBuildNumberAvailab......
  • VMware ESXi 6.7 U3 Final - ESXi 6 系列最终版下载
    VMwareESXi6.7U3Final-ESXi6系列最终版下载VMwareESXi6Standard请访问原文链接:https://sysin.org/blog/vmware-esxi-6/,查看最新版。原创作品,转载请保留出处。作者主页:sysin.orgVersionReleaseNameReleaseDateBuildNumberInstallerBuildNumberAvailab......
  • Linux 安装已下载的 dotnet-sdk-6.0
    1.下载地址 https://dotnet.microsoft.com/zh-cn/download/dotnet 2.用工具 FileZilla(类似FTP功能)上传到Linux系统(用root登录) 3.用工具 Xshell7(类似Cmd功能) (用root登录)3.1切换到上传的目录下:  cd /root/下载3.2创建安装目录:     ......
  • sqli-lib通关笔记
    因为好久都没有联系过SQL注入了,打算重新拾起渗透方向的能力,去他妈的运维,老子才不要做运维,被傻逼公司给骗了,当了一年的运维,白白浪费了一年。第一关先查看一下代码: 真正的关于注入的核心语句就只有中间的select查询语句,一是先看是什么闭合,第二再看有没有过滤没有任何的......
  • NPU-ISP技术图例
    NPU-ISP技术图例           参考文献链接https://www.zhihu.com/question/506376849......