C++-এ বাইনারি ট্রিতে ভালো নোড গণনা

একটি বাইনারি ট্রিতে একটি নোড X ভালো নোড যদি রুট থেকে X পর্যন্ত পথে X চেয়ে বড় কোনো মান থাকে না। মোট কতটি ভালো নোড আছে তা বের করতে হবে।

ইনপুট ট্রি চিত্রে দেখানো হয়েছে → আউটপুট: 4

সমাধানের ধাপগুলো (DFS):

dfs(node, maxVal) ফাংশন: বর্তমান পথে সর্বোচ্চ মান পাস করব
যদি node->val >= maxVal হয়, তবে ভালো নোড, কাউন্ট বাড়াব
নতুন maxVal = max(maxVal, node->val) দিয়ে চাইল্ডে রিকার্স করব
মেইন থেকে dfs(root, INT_MIN) কল করব

উদাহরণ

নিচের কোডটি দেখুন −

#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;
    }
};

int 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}