การนับรูทค่าสูงสุดในทรีไบนารีใน C++

สมมติว่าเรามีรูทแบบไบนารี เราต้องนับจำนวนโหนดที่มีค่ามากกว่าหรือเท่ากับค่าของลูกหลานทั้งหมด

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

จากนั้นผลลัพธ์จะเป็น 4 เนื่องจากโหนดทั้งหมดยกเว้น 3 เป็นไปตามเกณฑ์

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

กำหนดฟังก์ชัน dfs() ซึ่งจะใช้โหนด
ถ้าโหนดไม่เป็นโมฆะ −
- คืนค่า 0
l :=dfs(ซ้ายของโหนด)
r :=dfs(ทางขวาของโหนด)
ถ้า val ของโหนด>=สูงสุดของ l และ r แล้ว −
- (เพิ่มการถอยกลับโดย 1)
x :=val สูงสุดของโหนด l และ r
ผลตอบแทน x
จากวิธีหลัก ให้ทำดังนี้
ยกเลิก :=0
dfs(root)
รีเทิร์น

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

ตัวอย่าง

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

อินพุต

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