मान लीजिए हमारे पास एक बाइनरी ट्री है, जहां प्रत्येक नोड का मान या तो 0 या 1 है। हमें वही ट्री ढूंढना है जहां 1 न रखने वाले हर उपट्री को हटा दिया गया हो।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
एक रिकर्सिव विधि solve() परिभाषित करें, यह नोड लेगी। विधि इस तरह होगी -
यदि नोड null है, तो null लौटाएं
नोड का left := solve(nोड का left)
नोड का right := solve(नोड का right)
यदि नोड का left null है और नोड का right भी null है और नोड का मान 0 है, तो null लौटाएं
नोड लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h> using namespace std; class TreeNode{ public: int val; TreeNode *left, *right; TreeNode(int data){ val = data; left = NULL; right = NULL; } }; void inorder(TreeNode *root){ if(root){ inorder(root->left); cout << root->val << ", "; inorder(root->right); } } class Solution { public: TreeNode* pruneTree(TreeNode* node) { if(!node)return NULL; node->left = pruneTree(node->left); node->right = pruneTree(node->right); if(!node->left && !node->right && !node->val){ return NULL; } return node; } }; main(){ TreeNode *root = new TreeNode(1); root->left = new TreeNode(1); root->right = new TreeNode(0); root->left->left = new TreeNode(1); root->left->right = new TreeNode(1); root->right->left = new TreeNode(0); root->right->right = new TreeNode(1); root->left->left->left = new TreeNode(0); Solution ob; inorder(ob.pruneTree(root)); } इनपुट
TreeNode *root = new TreeNode(1); root->left = new TreeNode(1); root->right = new TreeNode(0); root->left->left = new TreeNode(1); root->left->right = new TreeNode(1); root->right->left = new TreeNode(0); root->right->right = new TreeNode(1); root->left->left->left = new TreeNode(0);
आउटपुट
1, 1, 1, 1, 0, 1,
