Computer >> Máy Tính >  >> Lập trình >> C ++

Xóa các nút cây trong C ++

Giả sử chúng ta có một cây, cây này bắt nguồn từ nút 0, điều này được đưa ra như sau -

  1. Số nút là nút
  2. Giá trị của nút thứ i là giá trị [i]
  3. Cấp độ gốc của nút thứ i là cấp độ cha [i]

Chúng ta phải loại bỏ mọi cây con có tổng giá trị của các nút bằng 0, sau khi thực hiện điều đó trả về số lượng nút còn lại trong cây. Vì vậy, nếu cây như -

Xóa các nút cây trong C ++

Có 7 nút, đầu ra sẽ là 2

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • Tạo một bản đồ có tên là con
  • xác định một phương thức được gọi là dfs (), phương thức này sẽ nhận nút, một giá trị mảng và đồ thị
  • temp:=a pair (value [node], 1)
  • cho tôi trong phạm vi từ 0 đến kích thước của biểu đồ [nút]
    • temp2:=dfs (graph [node, i], value, graph)
    • tăng đầu tiên theo nhiệt độ đầu tiên của nhiệt độ2, tăng thứ hai lên từng thứ hai của nhiệt độ2
  • nếu đầu tiên của nhiệt độ là 0, thì ans:=ans - thứ hai của nhiệt độ, đặt thứ hai của nhiệt độ:=0
  • nhiệt độ trở lại
  • Từ phương thức main, nó sẽ lấy các nút, mảng cha và mảng giá trị
  • n:=số giá trị có trong mảng giá trị
  • ans:=n
  • xác định một đồ thị mảng có kích thước n + 1
  • cho tôi trong phạm vi từ 1 đến n - 1
    • chèn i vào biểu đồ [cha [i]]
  • dfs (0, value, graph)
  • trả lại ans

Ví dụ (C ++)

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

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

Đầu vào 

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

Đầu ra 

2