นับโหนดที่ดีในไบนารีทรีใน C ++

สมมติว่าเรามีไบนารีทรี โหนด X ในทรีมีชื่อว่า ดี เมื่ออยู่ในเส้นทางจากรูทไปยัง X ไม่มีโหนดที่มีค่ามากกว่า X ในที่นี้ เราต้องหาจำนวนโหนดที่ดีในไบนารีทรี

ดังนั้นหากอินพุตเป็นแบบนั้น

แล้วผลลัพธ์จะเป็น 4 โหนดสีเป็นโหนดที่ดี

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน dfs() ซึ่งจะใช้โหนด val

• ถ้าโหนดเป็นโมฆะ −

  • กลับ

• ret :=ret + (1 เมื่อ val <=val ของโหนด มิฉะนั้น 0)

• dfs (ด้านซ้ายของโหนด ค่าสูงสุดของ val และ val ของโหนด)

• dfs(ด้านขวาของโหนด ค่าสูงสุดของ val และ val ของโหนด)

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• ยกเลิก :=0

• dfs(root, -inf)

• รีเทิร์น

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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