home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Counting Maximal Value Roots in Binary Tree in C++

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

เช่น ต้นไม้ที่มีโครงสร้างดังภาพ ผลลัพธ์จะเป็น 4 เนื่องจากทุกโหนดยกเว้น 3 ตรงตามเงื่อนไข

ขั้นตอนการแก้ปัญหา

  • ฟังก์ชัน dfs(node): คืนค่าค่าสูงสุดในซับทรีที่รากคือ node
    • ถ้า node เป็น null: return 0
    • l = dfs(node->left), r = dfs(node->right)
    • ถ้า node->val >= max(l, r): เพิ่ม contet ret
    • return max(node->val, l, r)
  • จาก main: ret = 0, เรียก dfs(root), คืนค่า ret

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) { val = data; left = 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++;
        return max({node->val, l, r});
    }
    int solve(TreeNode* root) {
        ret = 0;
        dfs(root);
        return ret;
    }
};

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

เอาต์พุต

4