数据结构
网络
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 次浏览
广告