C++에서 트리 노드 삭제

트리가 있다고 가정하고 이 트리는 노드 0에 뿌리를 두고 있으며 다음과 같이 주어집니다. -

1. 노드 수는 노드입니다.
2. i번째 노드의 값은 value[i]입니다.
3. i번째 노드의 부모는 부모[i]

노드 값의 합이 0인 모든 하위 트리를 제거해야 트리에 남아 있는 노드 수를 반환합니다. 트리가 다음과 같다면 -

7개의 노드가 있고 출력은 2

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 어린이라는 지도 만들기
• dfs()라는 메서드를 정의하면 노드, 배열 값 및 그래프가 필요합니다.
• temp :=쌍 (값[노드], 1)
• 0 범위에서 그래프[노드] 크기까지의 i에 대해
  • temp2 :=dfs(그래프[노드, i], 값, 그래프)
  • temp2의 첫 번째만큼 증가, temp2의 두 번째 증가
• temp의 첫 번째 값이 0이면 ans :=ans – 두 번째 temp, 설정 두 번째 temp :=0
• 반환 온도
• 메인 메소드에서 노드, 상위 배열 및 값 배열을 사용합니다.
• n :=값 배열에 있는 값의 수
• an :=n
• n + 1 크기의 배열 그래프 정의
• 1 ~ n – 1 범위의 i에 대해
  • 그래프에 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