Medium

题目描述

给你一个二叉树的根节点 root 和一个整数 target，请你删除所有值为 target 的叶子节点。

注意，一旦删除值为 target 的叶子节点，它的父节点就可能变成叶子节点；如果新叶子节点的值恰好也是 target，那么这个节点也应该被删除（你需要不断重复相同的操作，直到不能继续删除）。

示例 1：

输入：root = [1,2,3,2,null,2,4], target = 2
输出：[1,null,3,null,4]
解释：上面左边的图中，绿色节点为叶子节点，且它们的值与 target 相同（都是 2），它们会被删除，得到中间的图。
删除后，节点 2 再次变成叶子节点，继续删除，最后得到右边的图。

示例 2：

输入：root = [1,3,3,3,2], target = 3
输出：[1,3,null,null,2]

示例 3：

输入：root = [1,2,null,2,null,2], target = 2
输出：[1]
解释：先删除最右边的 2，然后再删除中间的 2，最后删除最左边的 2。

提示：

  • 树中节点数目在范围 [1, 3000] 内
  • 1 <= Node.val, target <= 1000

解题思路

这道题需要删除所有值为 target 的叶子节点，关键在于理解删除的连锁反应：当一个叶子节点被删除后，它的父节点可能也变成叶子节点，如果父节点的值也是 target，那么也要被删除。

核心思路： 使用深度优先搜索（DFS）的后序遍历。我们需要先处理子树，然后再处理当前节点。这样可以确保在判断当前节点是否为叶子节点时，所有应该被删除的子节点都已经被处理了。

算法步骤：

  1. 递归处理左子树和右子树
  2. 更新当前节点的左右子树指针（因为子节点可能被删除）
  3. 检查当前节点是否为叶子节点且值等于 target
  4. 如果是，则返回 null（删除该节点）；否则返回当前节点

边界情况处理：

  • 如果根节点本身就是值为 target 的叶子节点，需要返回 null
  • 需要正确处理单个节点的情况

这种方法确保了删除操作的正确性，因为我们总是从叶子节点开始删除，逐层向上处理。

代码实现

class Solution {
public:
    TreeNode* removeLeafNodes(TreeNode* root, int target) {
        if (!root) return nullptr;
        
        // 先递归处理左右子树
        root->left = removeLeafNodes(root->left, target);
        root->right = removeLeafNodes(root->right, target);
        
        // 如果当前节点是叶子节点且值等于target，删除它
        if (!root->left && !root->right && root->val == target) {
            return nullptr;
        }
        
        return root;
    }
};

class Solution:
    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:
        if not root:
            return None
        
        # 先递归处理左右子树
        root.left = self.removeLeafNodes(root.left, target)
        root.right = self.removeLeafNodes(root.right, target)
        
        # 如果当前节点是叶子节点且值等于target，删除它
        if not root.left and not root.right and root.val == target:
            return None
        
        return root

public class Solution {
    public TreeNode RemoveLeafNodes(TreeNode root, int target) {
        if (root == null) return null;
        
        // 先递归处理左右子树
        root.left = RemoveLeafNodes(root.left, target);
        root.right = RemoveLeafNodes(root.right, target);
        
        // 如果当前节点是叶子节点且值等于target，删除它
        if (root.left == null && root.right == null && root.val == target) {
            return null;
        }
        
        return root;
    }
}

var removeLeafNodes = function(root, target) {
    if (!root) return null;
    
    root.left = removeLeafNodes(root.left, target);
    root.right = removeLeafNodes(root.right, target);
    
    if (!root.left && !root.right && root.val === target) {
        return null;
    }
    
    return root;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

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