数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中删除树节点
假设我们有一棵树，这棵树的根节点为0，如下所示：
- 节点数为nodes
- 第i个节点的值为value[i]
- 第i个节点的父节点为parent[i]
我们必须移除所有节点值之和为0的子树，之后返回树中剩余的节点数。例如：
共有7个节点，输出结果为2
为了解决这个问题，我们将遵循以下步骤：
- 创建一个名为children的映射
- 定义一个名为dfs()的方法，它将接收节点、一个值数组和图作为参数
- temp := 一个pair (value[node], 1)
- 对于i in range 0 to size of graph[node]
- temp2 := dfs(graph[node, i], value, graph)
- 将temp的第一项加上temp2的第一项，将temp的第二项加上temp2的第二项
- 如果temp的第一项为0，则ans := ans – temp的第二项，并将temp的第二项设置为0
- 返回temp
- 在主方法中，它将接收节点数、父节点数组和值数组
- n := 值数组中存在的数值个数
- ans := n
- 定义一个大小为n + 1的数组graph
- 对于i in range 1 to n – 1
- 将i插入到graph[parent[i]]中
- dfs(0, value, graph)
- 返回ans
示例（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
更新于：2020年4月30日
210 次浏览
广告