ให้ N-ary tree และตัวเลข n หาจำนวนโหนดที่มีค่ามากกว่า n
ตัวอย่าง:
Input: tree = [[4], [1, 2], [3, 5]], n = 2 Output: 3
อัลกอริทึม
- สร้างโครงสร้าง Node มี data และ vector<Node*> child
- ฟังก์ชัน getGreaterElementsCount(root, n):
- ถ้า root == NULL คืน 0
- count = (root->data > n) ? 1 : 0
- วนลูปลูกทั้งหมด count += recursive call
- คืนค่า count
การเขียนโปรแกรม 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++; for (int i = 0; i < root->child.size(); i++) { count += getGreaterElementsCount(root->child[i], 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
