Sponsored
Sponsored
This approach involves using a recursive DFS to navigate through the binary tree. We start from the root and check the leaf nodes. If a leaf node matches the target value, we remove it by returning null; otherwise, return the node itself. This should also be applied recursively to handle cases where removing a leaf creates another leaf node which must also be removed.
Time Complexity: O(n), where n is the number of nodes in the tree, since we visit each node exactly once.
Space Complexity: O(h), where h is the height of the tree, due to the recursion stack.
1class TreeNode {
2 int val;
3 TreeNode left;
4 TreeNode right;
5 TreeNode() {}
6 TreeNode(int val) { this.val = val; }
7 TreeNode(int val, TreeNode left, TreeNode right) {
8 this.val = val;
9 this.left = left;
10 this.right = right;
11 }
12}
13
14class Solution {
15 public TreeNode removeLeafNodes(TreeNode root, int target) {
16 if (root == null) return null;
17 root.left = removeLeafNodes(root.left, target);
18 root.right = removeLeafNodes(root.right, target);
19 if (root.left == null && root.right == null && root.val == target) {
20 return null;
21 }
22 return root;
23 }
24}This Java approach similarly employs a recursive strategy to traverse the tree and remove leaf nodes with the specified target value. After checking and potentially modifying the left and right children, we verify whether the current root is a target leaf and remove it if needed.
This approach uses an iterative post-order traversal to visit the nodes of the binary tree. By using a stack, we can simulate the recursive process, ensuring we evaluate and remove leaf nodes correctly by visiting left, right, and then parent nodes.
Time Complexity: O(n), each node is visited once.
Space Complexity: O(h), where h is the height of the tree, required for the stack.
1public class TreeNode {
2 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
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);
if (root.left == null && root.right == null && root.val == target) {
return null;
}
return root;
}
}In C#, this solution also modifies the tree recursively, aiming for consistency across all solutions. Nodes are examined left to right recursively, similar to Java and Python, and removed if they are leaf nodes with the target value.