八宝山做网站公司,海外网络推广培训,仙桃做网站的公司,中国建筑第八工程局招聘信息给你二叉树的根节点 root 和一个整数 limit #xff0c;请你同时删除树中所有 不足节点 #xff0c;并返回最终二叉树的根节点。假如通过节点 node 的每种可能的 “根-叶” 路径上值的总和全都小于给定的 limit#xff0c;则该节点被称之为 不足节点 #xff0c;需要被删除…给你二叉树的根节点 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.添加一个递归参数 sumPath表示从根到当前节点的路径和
(O_O)?疑惑
① 叶子节点什么时候能删除② 非叶子节点若还有儿子未被删除它能否被删除③ 非叶子节点的儿子都被删除意味着什么 思路和分析
① 对于一个叶子节点node从根到这个叶子节点leaf的路径仅有一条那么这条路径的元素和小于limit就删掉该叶子节点② 对于一个非叶子节点node若 node 还有儿子未被删除那么 node 就不能被删除 反证法证明设把 node 删除那么经过 node 的所有路径和都小于 limit这意味着经过 node 的儿子路径和也是小于 limit那么 node 的儿子也应当被删除矛盾故 node 不能被删除③ 对于一个非叶子节点node的儿子都被删除意味着经过 node 的所有儿子的路径和都小于 limit。这等价于经过 node 的所有路径和都小于 limit故 node 也应当被删除。 总结当且仅当 node 的所有儿子都被删除才可删除非叶节点 node 算法1添加一个递归参数 sumPath,表示从根到当前节点的路径和
① 如果当前节点是叶子节点leaf且此时 sumPath limit说明从根到这个叶子节点的路径和小于limit那么删除这个叶子节点② 如果当前节点是非叶子节点node继续往下递归node的左儿子为leaf时且经过 node 的左儿子路径和也是小于limit就删除这个儿子node的右儿子为leaf时且经过 node 的右儿子路径和也是小于limit就删除这个儿子
if(node-left dfs(node-left,limit,sumPath)false) { // 左node-left nullptr;
}
if(node-right dfs(node-right,limit,sumPath)false) { // 右node-right nullptr;
}
③ 如果当前节点是非叶子节点node且左右儿子都为空那么就删除 node返回 false 否则返回 true
return node-left || node-right; C代码
class Solution {
public:bool dfs(TreeNode* node,int limit,int sumPath) {sumPath node-val;if(node-left node-right) {return sumPathlimit;} if(node-left dfs(node-left,limit,sumPath)false) { // 左node-left nullptr;}if(node-right dfs(node-right,limit,sumPath)false) { // 右node-right nullptr;}return node-left || node-right;}TreeNode* sufficientSubset(TreeNode* root, int limit) {return dfs(root,limit,0) ?root:nullptr;}
};
① 图解示例一 ② 图解示例三 方式2.从 limit 中减去当前节点值
先比方式1可以少一个参数 sumPath
class Solution {
public:bool dfs(TreeNode* node,int limit) {limit-node-val;if(node-left node-right) {return limit0?false:true;} if(node-left dfs(node-left,limit)false) { // 左node-left nullptr;}if(node-right dfs(node-right,limit)false) { // 右node-right nullptr;}return node-left || node-right;}TreeNode* sufficientSubset(TreeNode* root, int limit) {return dfs(root,limit) ?root:nullptr;}
};
方式3. 从 limit 中减去当前节点值直接调用 sufficientSubset
如果当前节点是叶子且此时 limit 0说明从根到这个叶子的路径和小于 limit 那么删除这个叶子如果当前节点不是叶子那么往下递归更新它的左儿子为对左儿子调用 sufficientSubset 的结果更新它的右儿子为对右儿子调用 sufficientSubset 的结果如果左右儿子都为空那么就删除当前节点返回空否则不删返回当前节点 此段文字来自以下作者 作者灵茶山艾府 链接https://leetcode.cn/problems/insufficient-nodes-in-root-to-leaf-paths/description/ class Solution {
public:TreeNode* sufficientSubset(TreeNode* root, int limit) {limit-root-val;if(root-left root-right) { // root 是叶子return limit 0 ? nullptr : root;} if(root-left) { // 左root-left sufficientSubset(root-left,limit);}if(root-right) { // 右root-right sufficientSubset(root-right,limit);}// 如果有儿子没被删除就不删 root否则删 rootreturn root-left || root-right ?root:nullptr;}
};
参考和推荐文章
1080. 根到叶路径上的不足节点 - 力扣LeetCodehttps://leetcode.cn/problems/insufficient-nodes-in-root-to-leaf-paths/solutions/2278769/jian-ji-xie-fa-diao-yong-zi-shen-pythonj-64lf/
