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 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7def removeLeafNodes(root, target):
8 if not root:
9 return None
10 root.left = removeLeafNodes(root.left, target)
11 root.right = removeLeafNodes(root.right, target)
12 if not root.left and not root.right and root.val == target:
13 return None
14 return rootIn this solution, we recursively dive into the left and right subtrees to remove the leaf nodes with the target value. After modifying both subtrees, we check if the current node has become a leaf with the target value and delete it if so.
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.