बाइनरी ट्री दिया गया है। उन नोड्स की गिनती करें जिनका मान उनके सभी वंशजों के मानों से बड़ा या बराबर हो।
पोस्ट-ऑर्डर DFS: प्रत्येक नोड अपने सबट्री का अधिकतम मान वापस करता है। यदि नोड का मान ≥ max(बाएं_अधिकतम, दाएं_अधिकतम) तो गिनती बढ़ाएं।
उदाहरण ट्री के लिए आउटपुट 4 (नोड 3 को छोड़कर सभी)।
C++ कार्यान्वयन
#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;
}
};
int 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);
return 0;
}
इनपुट
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
