मान लीजिए हमारे पास एक बाइनरी ट्री है, ट्री में एक नोड X को अच्छा कहा जाता है जब रूट से X तक के पथ में कोई ऐसा नोड नहीं होता जिसका मान X से अधिक हो। यहाँ हमें बाइनरी ट्री में अच्छे नोड्स की संख्या ढूंढनी है।
इसलिए, यदि इनपुट है,
तो आउटपुट 4 होगा, रंगीन नोड्स अच्छे नोड हैं।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
एक फ़ंक्शन dfs() परिभाषित करें, जो node, val लेगा,
यदि node null है, तो -
लौटें
ret := ret + (1 जब val <= node का मान, अन्यथा 0)
dfs(node का बायाँ भाग, max(val, node का मान))
dfs(node का दायाँ भाग, max(val, node का मान))
मुख्य विधि से निम्न करें -
ret := 0
dfs(root, -inf)
ret लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#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 insert(TreeNode **root, int val){ queue<TreeNode*> q; q.push(*root); while(q.size()){ TreeNode *temp = q.front(); q.pop(); if(!temp->left){ if(val != NULL) temp->left = new TreeNode(val); else temp->left = new TreeNode(0); return; }else{ q.push(temp->left); } if(!temp->right){ if(val != NULL) temp->right = new TreeNode(val); else temp->right = new TreeNode(0); return; }else{ q.push(temp->right); } } } TreeNode *make_tree(vector<int> v){ TreeNode *root = new TreeNode(v[0]); for(int i = 1; i<v.size(); i++){ insert(&root, v[i]); } return root; } class Solution { public: int ret; void dfs(TreeNode* node, int val){ if (!node) return; ret += val <= node->val; dfs(node->left, max(val, node->val)); dfs(node->right, max(val, node->val)); } int goodNodes(TreeNode* root){ ret = 0; dfs(root, INT_MIN); return ret; } }; main(){ Solution ob; vector<int> v = {3,1,4,3,NULL,1,5}; TreeNode *root = make_tree(v); cout << (ob.goodNodes(root)); }इनपुट
{3,1,4,3,NULL,1,5}आउटपुट
4
