给你二叉树的根节点 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