Given a binary tree root
and an integer target
, delete all the leaf nodes with value target
.
Note that once you delete a leaf node with value target
, if its parent node becomes a leaf node and has the value target
, it should also be deleted (you need to continue doing that until you cannot)
Problem is actually easy level and is easy to understand.
This is similar to House robber-III problem as to start trimming from leaf nodes and go up.
So post-order DFS approach is better for this problem.
Below is the C solution:
void rmLfNodes(struct TreeNode *nd, struct TreeNode *parent, bool left, int target){
/* if no node or value not matching */
if (!nd) return;
rmLfNodes(nd->left, nd, 1, target);
rmLfNodes(nd->right, nd, 0, target);
if (!nd->left && !nd->right && nd->val == target){
if (left)
parent->left = NULL;
else
parent->right = NULL;
free(nd);
}
return;
}struct TreeNode* removeLeafNodes(struct TreeNode* root, int target){
if (!root) return NULL;
rmLfNodes(root->left, root, 1, target);
rmLfNodes(root->right, root, 0, target);
if (!root->left && !root->right && root->val == target)
return NULL;
return root;
}
I think we can still optimize, please provide your feedback.
Below is Python sol, we can still optimize by passing or checking parent as NULL
class Solution(object):
def helper(self, nd, parent, target):
if (nd is None):
return
self.helper(nd.left, nd, target)
self.helper(nd.right, nd, target)
if ((nd.left is None) and (nd.right is None) and
(nd.val == target)):
if (parent.left == nd):
parent.left = None
else:
parent.right = None
return
def removeLeafNodes(self, root, target):
"""
:type root: TreeNode
:type target: int
:rtype: TreeNode
"""
if (root is None):
return None
self.helper(root.left, root, target)
self.helper(root.right, root, target)
if ((root.left == None) and (root.right == None) and
(root.val == target)):
return None
return root;