मान लीजिए कि हमारे पास एक बाइनरी ट्री रूट है; हमें नोड्स की संख्या गिननी होगी जहां इसका मान इसके सभी वंशजों के मूल्यों से अधिक या बराबर है।
तो, अगर इनपुट पसंद है
तो आउटपुट 4 होगा क्योंकि 3 को छोड़कर सभी नोड्स, यह मानदंडों को पूरा करता है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
फ़ंक्शन को परिभाषित करें dfs(), यह नोड लेगा,
-
यदि नोड शून्य नहीं है, तो -
-
वापसी 0
-
-
l :=dfs (नोड के बाएं)
-
r :=dfs (नोड के दाएं)
-
यदि नोड का मान>=अधिकतम l और r, तो −
-
(रिटर्न 1 से बढ़ाएं)
-
-
x :=नोड, l और r के अधिकतम मान
-
वापसी x
-
मुख्य विधि से, निम्न कार्य करें,
-
रिट:=0
-
dfs(रूट)
-
वापसी रिट
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int data) {
val = data;
left = NULL;
right = NULL;
}
};
class Solution {
public:
int ret;
int dfs(TreeNode* node){
if(!node)
return 0;
int l = dfs(node->left);
int r = dfs(node->right);
if(node->val >= max(l, r)) {
ret++;
}
int x = max({node->val, l, r});
return x;
}
int solve(TreeNode* root) {
ret = 0;
dfs(root);
return ret;
}
};
main(){
Solution ob;
TreeNode *root = new TreeNode(7);
root->left = new TreeNode(4);
root->right = new TreeNode(3);
root->right->left = new TreeNode(7);
root->right->right = new TreeNode(5);
cout << (ob.solve(root));
} इनपुट
TreeNode *root = new TreeNode(7); root->left = new TreeNode(4); root->right = new TreeNode(3); root->right->left = new TreeNode(7); root->right->right = new TreeNode(5);
आउटपुट
4