https://leetcode.com/problems/binary-tree-pruning/
Problem Statement:
We are given the head node root of a binary tree, where additionally every node's value is either a 0 or a 1.
Return the same tree where every subtree (of the given tree) not containing a 1 has been removed.
(Recall that the subtree of a node X is X, plus every node that is a descendant of X.)
Examples
1:
2:
3:
Idea:
The idea here is to make a recursive helper function that will tell us if a given subtree contains a zero. We call this function on the root, and it will be recursively called on the subtrees. If we find at any point a given subtree contains a zero, that branch is effectively removed by setting the subtree to nullptr.
At the end, all subtrees that contain zero will be removed.
Solution:
class Solution {
public:
bool has_one(TreeNode* root) {
if(root == nullptr) return false;
bool left = has_one(root->left);
bool right = has_one(root->right);
if(!left) root->left = nullptr;
if(!right) root->right = nullptr;
return left || right || root->val == 1;
}
TreeNode* pruneTree(TreeNode* root) {
return has_one(root) ? root: nullptr;
}
};
Comments
Nothing yet.