ลบโหนดทรีใน C ++

สมมุติว่าเรามีต้นไม้ต้นหนึ่ง ต้นไม้นี้ถูกรูทที่โหนด 0 ซึ่งจะมีดังต่อไปนี้ -

1. จำนวนโหนดคือโหนด
2. ค่าของโหนด ith คือค่า[i]
3. พาเรนต์ของโหนด ith คือพาเรนต์[i]

เราต้องลบทรีย่อยทั้งหมดที่มีผลรวมของค่าของโหนดเป็น 0 หลังจากที่ทำเช่นนั้นแล้วจะคืนค่าจำนวนโหนดที่เหลืออยู่ในทรี ดังนั้นถ้าต้นไม้เป็นเหมือน −

มี 7 โหนด เอาต์พุตจะเป็น 2

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

• สร้างแผนที่ชื่อเด็ก
• กำหนดวิธีการที่เรียกว่า dfs() ซึ่งจะรับโหนด ค่าอาร์เรย์ และกราฟ
• อุณหภูมิ :=คู่ (ค่า[โหนด], 1)
• สำหรับ i ในช่วง 0 ถึงขนาดของกราฟ[โหนด]
  • temp2 :=dfs(graph[node, i], value, กราฟ)
  • เพิ่มครั้งแรกก่อน temp2 เพิ่มวินาทีทีละวินาทีของ temp2
• ถ้าตัวแรกของ temp เป็น 0 แล้ว ans :=ans – วินาทีของ temp ให้ตั้งค่าวินาทีของ temp :=0
• อุณหภูมิกลับ
• จากวิธีหลัก จะใช้โหนด อาร์เรย์พาเรนต์ และอาร์เรย์ของค่า
• n :=จำนวนค่าที่มีอยู่ในอาร์เรย์ค่า
• ตอบ :=น
• กำหนดกราฟอาร์เรย์ขนาด n + 1
• สำหรับ i ในช่วง 1 ถึง n – 1
  • แทรก i ลงในกราฟ[พาเรนต์[i]]
• dfs(0, ค่า, กราฟ)
• คืนสินค้า

ตัวอย่าง(C++)

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   map <int, int> children;
   int ans;
   pair <int, int> dfs(int node, vector<int>& value, vector <int> graph[]){
      pair <int, int> temp = {value[node], 1};
      for(int i = 0; i < graph[node].size(); i++){
         pair <int, int> temp2 = dfs(graph[node][i], value, graph);
         temp.first += temp2.first;
         temp.second += temp2.second;
      }
      if(temp.first == 0){
         ans -= temp.second;
         temp.second = 0;
      }
      return temp;
   }
   int deleteTreeNodes(int nodes, vector<int>& parent, vector<int>& value) {
      int n = value.size();
      ans = n;
      children.clear();
      vector < int > graph[n + 1];
      for(int i = 1; i < n; i++){
         graph[parent[i]].push_back(i);
      }
      dfs(0, value, graph);
      return ans;
   }
};
main(){
   vector<int> v1 = {-1,0,0,1,2,2,2};
   vector<int> v2 = {1,-2,4,0,-2,-1,-1};
   Solution ob;
   cout << (ob.deleteTreeNodes(7,v1, v2));
}

อินพุต

7
[-1,0,0,1,2,2,2]
[1,-2,4,0,-2,-1,-1]

ผลลัพธ์

2