สมมติว่าเรามีต้นไม้ไบนารี เราวางกล้องไว้ที่โหนดของต้นไม้ ตอนนี้กล้องแต่ละตัวที่โหนดสามารถตรวจสอบพาเรนต์ ตัวเอง และลูกของมันได้ เราต้องหาจำนวนกล้องขั้นต่ำที่จำเป็นในการตรวจสอบโหนดทั้งหมดของทรี
ดังนั้นหากอินพุตเป็นเช่น −
แล้วเอาท์พุตจะเป็น 1 เพราะกล้องตัวเดียวก็เพียงพอที่จะติดตามได้ทั้งหมด
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดหนึ่งชุดที่เรียกว่าครอบคลุม ประเภท TreeNode (โหนดทรีมีซ้าย ขวา และฟิลด์ข้อมูล)
-
กำหนดฟังก์ชัน Solve() ซึ่งจะใช้โหนด พาเรนต์
-
ถ้าโหนดเป็นโมฆะ −
-
กลับ
-
-
แก้ (ด้านซ้ายของโหนด, โหนด)
-
แก้ (ด้านขวาของโหนด โหนด)
-
ถ้า (พาเรนต์เหมือนกับ NULL และ (โหนด ด้านซ้ายของโหนด ด้านขวาของโหนด) ไม่มีอะไรครอบคลุม −
-
(เพิ่มขึ้นทีละ 1)
-
แทรกโหนดเข้าปกคลุม
-
แทรกด้านซ้ายของโหนดลงในส่วนปกคลุม
-
แทรกทางขวาของโหนดในที่กำบัง
-
ใส่พาเรนต์เข้าไป
-
-
จากวิธีหลักให้ทำดังนี้
-
ตอบ :=0
-
แทรก NULL ลงในส่วนปกคลุม
-
แก้ (รูท, NULL)
-
กลับมาอีกครั้ง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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:
set<TreeNode*> covered;
int ans;
int minCameraCover(TreeNode* root){
covered.clear();
ans = 0;
covered.insert(NULL);
solve(root, NULL);
return ans;
}
void solve(TreeNode* node, TreeNode* parent){
if (!node)
return;
solve(node->left, node);
solve(node->right, node);
if ((parent == NULL && covered.find(node) == covered.end())
|| covered.find(node->left) == covered.end() || covered.find(node-
>right) == covered.end()) {
ans++;
covered.insert(node);
covered.insert(node->left);
covered.insert(node->right);
covered.insert(parent);
}
}
};
main(){
Solution ob;
TreeNode *root = new TreeNode(1);
root->left = new TreeNode(1);
root->left->left = new TreeNode(1); root->left->right = new
TreeNode(1);
cout << (ob.minCameraCover(root));
} อินพุต
[1,1,NULL,1,1]
ผลลัพธ์
1
