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.
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.