資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法律學C++ 中大於給定值的多叉樹中的節點數
給定一棵多叉樹和一個數字，我們需要計算比給定數字大的節點數。來看一個例子。
輸入
tree = [[4], [1, 2], [3, 5]] n = 2
輸出
3
有 3 個節點的值大於 n。
演算法
初始化多叉樹。
將計數初始化為 0。
當找到一個值大於 n 的節點時，將計數增加 1。
獲取當前節點的子節點。
迭代所有子節點並遞迴呼叫相同函式來計算節點。
返回計數。
實現
以下是上述演算法在 C++ 中的實現
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
vector<Node*> child;
};
Node* getNewNode(int data) {
Node* temp = new Node;
temp->data = data;
return temp;
}
int getGreaterElementsCount(Node* root, int n) {
if (root == NULL)
return 0;
int count = 0;
if (root->data > n) {
count++;
}
int nodeChildrenCount = root->child.size();
for (int i = 0; i < nodeChildrenCount; i++) {
Node* child = root->child[i];
count += getGreaterElementsCount(child, n);
}
return count;
}
int main() {
Node* root = getNewNode(1);
(root->child).push_back(getNewNode(2));
(root->child).push_back(getNewNode(3));
(root->child).push_back(getNewNode(4));
(root->child[0]->child).push_back(getNewNode(5));
(root->child[0]->child).push_back(getNewNode(5));
(root->child[1]->child).push_back(getNewNode(6));
(root->child[1]->child).push_back(getNewNode(6));
(root->child[1]->child).push_back(getNewNode(7));
(root->child[2]->child).push_back(getNewNode(8));
(root->child[2]->child).push_back(getNewNode(8));
(root->child[2]->child).push_back(getNewNode(9));
int n = 2;
cout << getGreaterElementsCount(root, n) << endl;
return 0;
}輸出
如果執行以上程式碼，你將得到以下結果。
10
更新於: 26-Oct-2021
306 次瀏覽
廣告