Đếm số mã tốt trong cây nhị phân trong C ++

Giả sử chúng ta có một cây nhị phân, một nút X trong cây được đặt tên là tốt khi trong đường dẫn từ gốc đến X không có nút nào có giá trị lớn hơn X. Ở đây chúng ta phải tìm số nút tốt trong cây nhị phân.

Vì vậy, nếu đầu vào giống như,

thì đầu ra sẽ là 4, các nút có màu là nút tốt.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm dfs (), hàm này sẽ lấy node, val,

• nếu nút là null, thì -

  • trở lại

• ret:=ret + (1 khi val <=val của nút, nếu không thì 0)

• dfs (bên trái của nút, tối đa của val và val của nút)

• dfs (bên phải của nút, tối đa của val và val của nút)

• Từ phương thức chính, hãy làm như sau -

• ret:=0

• dfs (root, -inf)

• trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

{3,1,4,3,NULL,1,5}

Đầu ra

4