資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告