在 C++ 中统计权重为完全平方数的节点

给定一棵二叉树及其节点的权重。目标是找到权重为完全平方数的节点的数量。如果权重为 36，则它是 6 的平方，因此该节点将被计算在内。

例如

输入

输入值后创建的树如下所示：

输出

Count the nodes whose weight is a perfect square are: 4

解释

我们得到了树的节点以及与每个节点关联的权重。现在我们检查节点的数字是否为完全平方数。

输入

输入值后创建的树如下所示：

输出

Count the nodes whose weight is a perfect square are: 2

解释

we are given with the tree nodes and the weights associated with each
node. Now we check whether the digits of nodes are perfect squares or not.

**以下程序中使用的方案如下**：

在这种方法中，我们将对树的图应用深度优先搜索 (DFS) 来遍历它并检查节点的权重是否为完全平方数。为此，我们将使用两个向量 Node_Weight(100) 和 edge_graph[100]。

• 使用节点的权重初始化 Node_Weight[]。

• 使用向量 edge_graph 创建一棵树。

• 取一个全局变量 square 并将其初始化为 0。

• 函数 check(int check_it) 获取一个整数，如果 check_it 是完全平方数，则返回 true。

• 取 total = sqrt(check_it)

• 现在，如果 (floor(total) != ceil(total)) 返回 true，则 total 不是完全平方数，返回 false。

• 否则返回 true。

• 函数 perfect_square(int node, int root) 获取树的节点和根节点，并返回给定树中权重为完全平方数的节点的数量。

• 如果 if(check(Node_Weight[node])) 返回 true，则递增 square。

• 使用 for 循环遍历向量 edge_graph[node] 中的树。

• 对向量中的下一个节点调用 perfect_square(it, node)。

• 在所有函数结束时，我们将得到 square 作为权重值为完全平方数的节点的数量。

示例

实时演示

#include <bits/stdc++.h>
using namespace std;
vector<int> Node_Weight(100);
vector<int> edge_graph[100];
int square = 0;
bool check(int check_it){
   double total = sqrt(check_it);
   if(floor(total) != ceil(total)){
      return false;
   }
   return true;
}
void perfect_square(int node, int root){
   if(check(Node_Weight[node])){
      square++;
   }
   for (int it : edge_graph[node]){
      if(it == root){
         continue;
      }
      perfect_square(it, node);
   }
}
int main(){
   //weight of the nodes
   Node_Weight[2] = 121;
   Node_Weight[1] = 81;
   Node_Weight[4] = 37;
   Node_Weight[3] = 25;
   Node_Weight[8] = 100;
   Node_Weight[9] = 701;
   //create graph edge
   edge_graph[2].push_back(1);
   edge_graph[2].push_back(4);
   edge_graph[4].push_back(3);
   edge_graph[4].push_back(8);
   edge_graph[8].push_back(9);
   perfect_square(2, 2);
   cout<<"Count the nodes whose weight is a perfect square are: "<<square;
   return 0;
}

输出

如果我们运行以上代码，它将生成以下输出：

Count the nodes whose weight is a perfect square are: 4

Sunidhi Bansal

更新于：2021 年 1 月 5 日

102 次查看

开启你的职业生涯

通过完成课程获得认证

开始学习