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

Cho cây gốc tại nút 0 với: số nút nodes, giá trị nút i là value[i], cha của nút i là parent[i]. Xóa mọi cây con có tổng giá trị = 0. Trả về số nút còn lại.

Ví dụ: 7 nút, kết quả = 2.

Giải thuật (DFS pós-order)

1. Xây dựng đồ thị con children từ mảng parent.
2. Hàm dfs(node) trả về cặp (tổng giá trị, số nút) của cây con.
3. Khởi tạo temp = (value[node], 1).
4. Duyệt con: cộng dồn kết quả dfs(con) vào temp.
5. Nếu temp.first == 0: trừ temp.second khỏi đáp án toàn cục ans, đặt temp.second = 0.
6. Trả về temp.
7. Main: ans = n, xây đồ thị, gọi dfs(0), trả về ans.

Ví dụ 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;
    }
};

int 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));
    return 0;
}

Đầu vào

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

Đầu ra

2