在 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 次檢視

開啟你的職業生涯

透過完成課程獲得認證

開始學習