上次编辑到这里，代码来自缓存 点击恢复默认模板
/**
* 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* sufficientSubset(TreeNode* root, int limit) {
}
};
golang 解法, 执行用时: 12 ms, 内存消耗: 6.9 MB, 提交时间: 2023-05-22 14:15:53
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sufficientSubset(root *TreeNode, limit int) *TreeNode {
if root == nil {
return nil
}
limit -= root.Val
if root.Left == root.Right { // root 是叶子
if limit > 0 { // 从根到叶子的路径和小于 limit，删除叶子
return nil
}
return root // 否则不删除
}
root.Left = sufficientSubset(root.Left, limit)
root.Right = sufficientSubset(root.Right, limit)
if root.Left == nil && root.Right == nil { // 如果儿子都被删除，就删 root
return nil
}
return root // 否则不删 root
}
java 解法, 执行用时: 0 ms, 内存消耗: 42.7 MB, 提交时间: 2023-05-22 14:15:40
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode sufficientSubset(TreeNode root, int limit) {
limit -= root.val;
if (root.left == root.right) // root 是叶子
// 如果 limit > 0 说明从根到叶子的路径和小于 limit，删除叶子，否则不删除
return limit > 0 ? null : root;
if (root.left != null) root.left = sufficientSubset(root.left, limit);
if (root.right != null) root.right = sufficientSubset(root.right, limit);
// 如果儿子都被删除，就删 root，否则不删 root
return root.left == null && root.right == null ? null : root;
}
}
python3 解法, 执行用时: 84 ms, 内存消耗: 18 MB, 提交时间: 2023-05-22 14:15:23
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:
limit -= root.val
if root.left is root.right: # root 是叶子
# 如果 limit > 0 说明从根到叶子的路径和小于 limit，删除叶子，否则不删除
return None if limit > 0 else root
if root.left: root.left = self.sufficientSubset(root.left, limit)
if root.right: root.right = self.sufficientSubset(root.right, limit)
# 如果有儿子没被删除，就不删 root，否则删 root
return root if root.left or root.right else None
输入：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]
输入：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]
输入：root = [5,-6,-6], limit = 0 输出：[]