814. Binary Tree Pruning
Given the root
of a binary tree, return the same tree where every subtree (of the given tree) not containing a 1
has been removed.
A subtree of a node node
is node
plus every node that is a descendant of node
.
Example 1:
Input: root = [1,null,0,0,1] Output: [1,null,0,null,1] Explanation: Only the red nodes satisfy the property "every subtree not containing a 1". The diagram on the right represents the answer.
Example 2:
Input: root = [1,0,1,0,0,0,1] Output: [1,null,1,null,1]
Example 3:
Input: root = [1,1,0,1,1,0,1,0] Output: [1,1,0,1,1,null,1]
Constraints:
- The number of nodes in the tree is in the range
[1, 200]
. Node.val
is either0
or1
.
solution :
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool inorder(TreeNode* root )
{
queue<TreeNode*>q;
q.push(root);
while(!q.empty())
{
TreeNode* temp = q.front();
if(temp->val == 1)
return true;
if(temp->left != NULL)
q.push(temp->left);
if(temp->right != NULL)
q.push(temp->right);
q.pop();
}
return false;
}
TreeNode* pruneTree(TreeNode* root) {
if(root->val == 0 && root->left ==NULL && root->right == NULL)
return NULL;
queue<TreeNode*>q;
q.push(root);
while(!q.empty())
{
TreeNode* temp = q.front();
if(temp->left != NULL)
{
if(!inorder(temp->left))
temp->left = NULL;
else
q.push(temp->left);
}
if(temp->right != NULL)
{
if(!inorder(temp->right))
temp->right = NULL;
else
q.push(temp->right);
}
q.pop();
}
if(root->val == 0 && root->left ==NULL && root->right == NULL)
return NULL;
return root;
}
};
Comments
Post a Comment