Prune The Tree

Given a binary tree where all nodes are either 0 or 1, prune the tree so that subtrees containing all 0s are removed.

For example, given the following tree:

Input:

   0
  / \
 1   0
    / \
   1   0
  / \
 0   0

should be pruned to:

   0
  / \
 1   0
    /
   1

We do not remove the tree at the root or its left child because it still has a 1 as a descendant.

Example:

Output: [0,1,0,null,null,1]

Approach

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode
{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
void printTree(TreeNode *root)
{
    queue<TreeNode *> q;
    q.push(root);
    vector<stringvec;
    while (!q.empty())
    {
        root = q.front();
        q.pop();
        if (root == NULL)
            vec.push_back("null");
        else
            vec.push_back(to_string(root->data));
        if (root != NULL)
        {
            q.push(root->left);
            q.push(root->right);
        }
    }
    int j = vec.size() - 1;
    while (j > 0 && vec[j] == "null")
        j--;
    vec.resize(j);
    for (int i = 0i < ji++)
        cout << vec[i] << ",";
    cout << vec[j];
}
TreeNode *pruneTree(TreeNode *root)
{
    if (root == NULL)
    {
        return NULL;
    }

    root->left = pruneTree(root->left);
    root->right = pruneTree(root->right);
    if (!root->left && !root->right && root->data == 0)
        return NULL;
    else
        return root;
}

int main()
{
    TreeNode *root = new TreeNode(0);
    root->left = new TreeNode(1);
    root->right = new TreeNode(0);
    root->right->left = new TreeNode(1);
    root->right->right = new TreeNode(0);
    root->right->left->left = new TreeNode(0);
    root->right->left->right = new TreeNode(0);

    TreeNode *res = pruneTree(root);
    cout << "[";
    printTree(res);
    cout << "]";
    return 0;
}


No comments:

Post a Comment