小型教育网站的开发与建设,湖南岳阳网站,东莞市人才服务中心官网,工商信息查询网官网1. 题目
给定一棵二叉树的根 root#xff0c;请你考虑它所有 从根到叶的路径#xff1a;从根到任何叶的路径。#xff08;所谓一个叶子节点#xff0c;就是一个没有子节点的节点#xff09;
假如通过节点 node 的每种可能的 “根-叶” 路径上值的总和全都小于给定的 lim…1. 题目
给定一棵二叉树的根 root请你考虑它所有 从根到叶的路径从根到任何叶的路径。所谓一个叶子节点就是一个没有子节点的节点
假如通过节点 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 [5,-6,-6], limit 0 输出[]
提示
给定的树有 1 到 5000 个节点
-10^5 node.val 10^5
-10^9 limit 10^9来源力扣LeetCode 链接https://leetcode-cn.com/problems/insufficient-nodes-in-root-to-leaf-paths 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
class Solution {int sum 0;//全局变量
public:TreeNode* sufficientSubset(TreeNode* root, int limit) {if(!root)return NULL;sum root-val;//加入路径sumif(!root-left !root-right)//叶子节点{if(sum limit)//需要删除节点{sum - root-val;return NULL;//一会父节点left或right指向nullptr}else//不删{sum - root-val;return root;//原封不动返回该节点}}else //非叶子节点继续往下{root-left sufficientSubset(root-left, limit);root-right sufficientSubset(root-right, limit);//左右都处理完了sum - root-val;//当前节点要return了减去它的值if(!root-left !root-right)//左右至少有一个被删了且现在没有子节点了return NULL;//它自己也需要被删elsereturn root;}}
};
