Đếm rễ giá trị tối đa trong cây nhị phân trong C ++

Giả sử chúng ta có gốc cây nhị phân; chúng ta phải đếm số lượng nút mà giá trị của nó lớn hơn hoặc bằng giá trị của tất cả các nút con của nó.

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

thì đầu ra sẽ là 4 vì tất cả các nút ngoại trừ 3, nó đáp ứng tiêu chí.

Để 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ẽ sử dụng nút,

• nếu nút không rỗng, thì -

  • trả về 0

• l:=dfs (bên trái của nút)

• r:=dfs (bên phải của nút)

• nếu val của nút> =tối đa của l và r, thì -

  • (tăng ret lên 1)

• x:=tối đa của val của nút, l và r

• trả lại x

• Từ phương thức chính, hãy thực hiện như sau,

• ret:=0

• dfs (gốc)

• trả lại ret

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

Ví dụ

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

Đầu vào

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

Đầu ra

4