删除给定值的叶子节点
难度:
标签:
题目描述
给你一棵以 root 为根的二叉树和一个整数 target ，请你删除所有值为 target 的 叶子节点 。
注意，一旦删除值为 target 的叶子节点，它的父节点就可能变成叶子节点；如果新叶子节点的值恰好也是 target ，那么这个节点也应该被删除。
也就是说，你需要重复此过程直到不能继续删除。
示例 1：
输入：root = [1,2,3,2,null,2,4], target = 2 输出：[1,null,3,null,4] 解释： 上面左边的图中，绿色节点为叶子节点，且它们的值与 target 相同（同为 2 ），它们会被删除，得到中间的图。 有一个新的节点变成了叶子节点且它的值与 target 相同，所以将再次进行删除，从而得到最右边的图。
示例 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）。
示例 4：
输入：root = [1,1,1], target = 1 输出：[]
示例 5：
输入：root = [1,2,3], target = 1 输出：[1,2,3]
提示：
1 <= target <= 1000- 每一棵树最多有
3000个节点。 - 每一个节点值的范围是
[1, 1000]。
代码结果
运行时间: 23 ms, 内存: 16.5 MB
/*
题目思路：
1. 使用递归函数来处理树的节点，判断是否需要删除。
2. 递归检查左子树和右子树，如果子节点是叶子节点且值等于target则删除。
3. 在递归结束后，判断当前节点是否成为新的叶子节点且值等于target，如果是则删除。
4. 反复上述过程直到树结构不再变化。
5. 使用Java Streams不能直接处理树结构，因此这部分依然用传统递归实现。
*/
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
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);
if (root.left == null && root.right == null && root.val == target) {
return null;
}
return root;
}
}
解释
方法:
该题解采用递归的方式来解决问题。递归的基本思路是从树的叶子节点开始向上工作，检查每个节点是否应该删除。首先，递归调用自身来处理当前节点的左右子节点。一旦左右子树处理完成，检查当前节点是否为叶子节点（即没有左右子节点），并且节点的值等于target。如果是，则将该节点删除（即返回None）。如果不是，则返回当前节点。这个过程会一直递归地向上回溯至树的根节点，确保所有符合条件的叶子节点都被删除。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在递归处理时，如何确保当一个节点成为新的叶子节点后，它会被检查是否需要删除？
▷🦆
递归删除操作何时停止？是否有可能形成无限递归的情况，特别是在某些特殊的树结构中？
▷🦆
节点被删除后，如何处理与其父节点的关联？在代码中具体是如何实现的？
▷🦆
对于非叶子节点，即使其值等于target，为什么不在首次递归中直接删除它？
▷