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.
1struct TreeNode {
2 int val;
3 TreeNode *left;
4 TreeNode *right;
5 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
6};
7
8class Solution {
9public:
10 TreeNode* removeLeafNodes(TreeNode* root, int target) {
11 if (!root) return nullptr;
12 root->left = removeLeafNodes(root->left, target);
13 root->right = removeLeafNodes(root->right, target);
14 if (!root->left && !root->right && root->val == target) {
15 delete root;
16 return nullptr;
17 }
18 return root;
19 }
20};In C++, the code follows the same recursive structure. Notice that when deleting a leaf node, it's essential to properly manage memory with 'delete'. The approach mirrors checking and removal by navigating both left and right sub-trees before determining if the current node qualifies for removal.
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.