資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中 N 叉樹的偶數大小子樹
在這個問題中，我們得到一個鄰接表，它表示一個 N 叉樹。我們的任務是找到 *N 叉樹中偶數大小子樹的數量*。
N 叉樹 **通常定義為節點的集合，通常以以下方式分層表示。**
樹從根節點開始。
樹的每個節點都維護一個指向其子節點的指標列表。
子節點的數量小於或等於 m。
讓我們舉個例子來理解這個問題，
輸入：
輸出：4
解釋：
以 7 為根的樹具有偶數大小。
以 2 為根的樹具有偶數大小。
以 0 為根的樹具有偶數大小。
以 3 為根的樹具有偶數大小。
解決方案方法 -
一個簡單的方法是計算給定節點的所有子節點，如果它是偶數，則增加 evenTreeCount。為此，我們將使用 DFS，並找到給定節點的子樹長度。
我們可以使用 *樹上的單次遍歷* 來做到這一點。透過遞迴地找到每個子節點的子樹的大小，然後檢查大小，如果它是偶數，則增加 evenTreeCount，否則保留它。
程式說明我們解決方案的工作原理，
示例
#include <bits/stdc++.h>
using namespace std;
int countEventSizeSubTree(vector<int> adj[], int n, int v, int& EvenCount){
int size = 1;
for (auto ele : adj[v]) {
size += countEventSizeSubTree(adj, n, ele, EvenCount);
}
if (size % 2 == 0)
EvenCount++;
return size;
}
int main(){
int n;
n = 10;
vector<int> adj[n + 1];
adj[7].push_back(2);
adj[7].push_back(9);
adj[2].push_back(0);
adj[2].push_back(1);
adj[9].push_back(3);
adj[3].push_back(8);
adj[0].push_back(5);
int EvenCount = 0;
countEventSizeSubTree(adj, n, 1, EvenCount);
cout<<"Even Size SubTree are "<<EvenCount;
return 0;
}輸出 -
Even Size SubTree are 0
更新於： 2021 年 1 月 22 日
122 次瀏覽
廣告