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.
1function TreeNode(val, left = null, right =
This JavaScript solution uses an iterative approach to simulate the post-order traversal. By attaching a dummy node to facilitate handling the root node, each node and its corresponding direction (left/right) are pushed onto a stack. As nodes are processed, if a node matches the target and is a leaf, it is removed by setting its parent's pointer to null.