Medium

题目描述

给你二叉树的根节点 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] 内
  • -10^5 <= Node.val <= 10^5
  • -10^9 <= limit <= 10^9

解题思路

这道题需要删除所有"不足节点"，即通过该节点的每条根到叶路径的和都小于 limit 的节点。

核心思路：

使用深度优先搜索（DFS）进行后序遍历，从叶子节点开始判断。关键是要理解"不足节点"的定义：一个节点是不足的，当且仅当通过它的所有根到叶路径的和都小于 limit。

算法步骤：

  1. 对于每个节点，递归处理其左右子树
  2. 如果是叶子节点，直接判断当前路径和是否满足条件
  3. 对于非叶子节点，需要检查处理后是否还有子节点存在：
    • 如果左右子树都被删除了，说明通过该节点的所有路径都不满足条件
    • 如果还有子节点存在，说明至少有一条路径满足条件

判断逻辑：

  • 叶子节点：当前路径和 >= limit 时保留
  • 非叶子节点：递归处理后至少有一个子节点存在时保留

这种方法确保了我们正确识别并删除所有不足节点，同时保留所有有效路径上的节点。

推荐解法： 后序遍历 DFS，时间复杂度 O(n)，空间复杂度 O(h)。

代码实现

class Solution {
public:
    TreeNode* sufficientSubset(TreeNode* root, int limit) {
        if (!root) return nullptr;
        
        // 如果是叶子节点，判断当前路径和是否满足条件
        if (!root->left && !root->right) {
            return root->val >= limit ? root : nullptr;
        }
        
        // 递归处理左右子树
        if (root->left) {
            root->left = sufficientSubset(root->left, limit - root->val);
        }
        if (root->right) {
            root->right = sufficientSubset(root->right, limit - root->val);
        }
        
        // 如果左右子树都被删除了，说明通过当前节点的所有路径都不满足条件
        if (!root->left && !root->right) {
            return nullptr;
        }
        
        return root;
    }
};

class Solution:
    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:
        if not root:
            return None
            
        # 如果是叶子节点，判断当前路径和是否满足条件
        if not root.left and not root.right:
            return root if root.val >= limit else None
        
        # 递归处理左右子树
        if root.left:
            root.left = self.sufficientSubset(root.left, limit - root.val)
        if root.right:
            root.right = self.sufficientSubset(root.right, limit - root.val)
        
        # 如果左右子树都被删除了，说明通过当前节点的所有路径都不满足条件
        if not root.left and not root.right:
            return None
            
        return root

public class Solution {
    public TreeNode SufficientSubset(TreeNode root, int limit) {
        if (root == null) return null;
        
        // 如果是叶子节点，判断当前路径和是否满足条件
        if (root.left == null && root.right == null) {
            return root.val >= limit ? root : null;
        }
        
        // 递归处理左右子树
        if (root.left != null) {
            root.left = SufficientSubset(root.left, limit - root.val);
        }
        if (root.right != null) {
            root.right = SufficientSubset(root.right, limit - root.val);
        }
        
        // 如果左右子树都被删除了，说明通过当前节点的所有路径都不满足条件
        if (root.left == null && root.right == null) {
            return null;
        }
        
        return root;
    }
}

var sufficientSubset = function(root, limit) {
    if (!root) return null;
    
    // 如果是叶子节点，判断当前路径和是否满足条件
    if (!root.left && !root.right) {
        return root.val >= limit ? root : null;
    }
    
    // 递归处理左右子树
    if (root.left) {
        root.left = sufficientSubset(root.left, limit - root.val);
    }
    if (root.right) {
        root.right = sufficientSubset(root.right, limit - root.val);
    }
    
    // 如果左右子树都被删除了，说明通过当前节点的所有路径都不满足条件
    if (!root.left && !root.right) {
        return null;
    }
    
    return root;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要访问树中的每个节点一次
空间复杂度O(h)递归调用栈的深度，h 为树的高度，最坏情况下为 O(n)

相关题目