C++ 打印二叉树的所有指数级别

在这个问题中，我们将打印二叉树的所有指数级别。

我们将使用层次遍历来遍历二叉树的每一层。然后，我们将使用该层的第一个元素找到最小的P和q值。在下一步中，我们可以检查其他级别的值是否是指数级别。

问题陈述

我们已经给出了一棵二叉树。我们需要打印二叉树的所有指数级别的值。如果二叉树的每个节点的级别的值等于PQ，则被称为指数级别。其中P是最小常数，Q是P的幂。

示例样本

输入

2
 /   \
3     9

输出

2 
3, 9

解释

在这里，树的两个层级都是指数的。第一层只包含单个值。因此，它将始终是指数级的。第二层的值是31和32。所以，每个值都以3Q的形式呈现。

输入

2
       /   \
     16    64
    /  \  /  \
   5  15 20  10
        /      \
       10       100

输出

25 
16 64 
10 100

解释

第一、第二和第四层是指数级的。

方法

在这个方法中，我们将获得每一层的所有节点。然后，我们将把第一个节点转换成PQ格式。然后，我们将检查是否可以将每个节点转换为PX格式。如果可以，我们将打印出该层。

算法

步骤1 - 调用executeSieve()函数，使用筛选算法在N + 1范围内找到质数。
步骤1.2 - 在executeSieve()函数中，定义一个大小为N + 1的check[]数组，并初始化为true，假设所有数字初始都是质数。
步骤1.3 - 使用循环在2到p * p的范围内进行迭代。在循环中，如果check[p]为true，则将p插入质数列表中。同时，在check[]数组中更新p的倍数的值为false。
步骤2 - 调用showExpoLevels()函数。在showExpoLevels()函数中，调用getHeight()函数获取二叉树的高度。在getHeight()函数中，递归遍历树并获取树的最大高度。
第3步 − 然后，创建一个大小等于树高度的队列（queue[]）数组，并将第一个元素初始化为根节点。然后，执行getExpLevels()函数。
第3.1步 − 在getExpLevels()函数中，创建一个level[]列表来存储每个层级的节点。
第3.2步 − 当索引小于大小时进行迭代。同时，使用嵌套循环来在索引小于临时大小的情况下遍历特定层级。
第3.3步 − 从队列的索引’ind’中取出第一个节点。将节点的值插入levels[]列表中。如果存在左右节点，则将它们插入队列的末尾。
步骤 3.4 − 增加 ‘ind’ 的值。
步骤 3.5 − 如果我们遍历过某个特定的级别，则调用 checkForExponential() 函数来检查当前级别是否是指数级别。
步骤 3.5.1 − 在 checkForExponential() 函数中，调用 getXValue() 函数获取 x 的值。
步骤 3.5.2 − 在 getXValue() 函数中，如果 n 为 1，则返回 1。
步骤 3.5.3 − 否则，取 n 的对数，并从 2 到 n 进行遍历以找到 log(n) 的基数。
步骤 3.5.4 − 取 q 的对数。将 log(n)/log(q) 进行除法。然后，取 (pow(q, int(power))，如果结果值等于 n，则从函数中返回 x。
Step 3.6 - 获得X值后，通过使用isVal()函数检查每个级别值是否为X的幂。
Step 3.6.1 - 在isVal()函数中，我们使用对数来检查是否可以将给定值格式化为X的幂。
Step 3.7 - 如果无法将任何级别值格式化为X的幂，则返回false。否则，最后返回true。
Step 4 - 如果级别是指数级别，打印所有级别的值。

示例

#include <bits/stdc++.h>
using namespace std;
int N = 1e6;

struct TreeNode {
   int val;
   struct TreeNode *left, *right;
};
TreeNode *newNode(int val) {
   TreeNode *temp = new TreeNode;
   temp->val = val;
   temp->left = temp->right = NULL;
   return (temp);
}
vector<int> prime;
void executeSieve() {
   // Initially, all numbers are prime
   bool check[N + 1];
   memset(check, true, sizeof(check));
   for (int p = 2; p * p <= N; p++) {
      if (check[p] == true) {
         prime.push_back(p);
         // Update multiple p
         for (int q = p * p; q <= N; q += p)
            check[q] = false;
      }
   }
}
// To check whether number x^n
bool is_val(int n, int x) {
   double n_log;
   // Get a log
   n_log = log10(n) / log10(x);
   int num = (int)(pow(x, int(n_log)));
   if (n == num)
      return true;
   return false;
}
int getXValue(int n) {
   if (n == 1)
      return 1;
   double logVal, logq, power;
   int x, number;
   logVal = log10(n);
   for (int q = 2; q <= n; q++) {
      logq = log10(q);
      power = logVal / logq;
      number = (int)(pow(q, int(power)));
      if (abs(number - n) < 1e-6) {
         x = q;
         break;
      }
   }
   return x;
}
bool checkForExponential(vector<int> &level) {
   // Get the value of X
   int x = getXValue(level[0]);
   for (int q = 1; q < level.size(); q++) {
      if (!is_val(level[q], x))
         return false;
   }
   return true;
}
void getExpLevels(struct TreeNode *root, struct TreeNode *queue[], int ind, int size) {
   vector<int> level;
   while (ind < size) {
      int tmp_size = size;
      while (ind < tmp_size) {
         struct TreeNode *temp = queue[ind];
         level.push_back(temp->val);
         if (temp->left != NULL)
            queue[size++] = temp->left;
         if (temp->right != NULL)
            queue[size++] = temp->right;
         // Increment ind
         ind++;
      }
      // check if the level is exponential
      if (checkForExponential(level)) {
         for (auto ele : level) {
            cout << ele << " ";
         }
         cout << endl;
      }
      level.clear();
   }
}
int getHeight(struct TreeNode *root) {
   // Base case
   if (root == NULL)
      return 0;
   return 1 + getHeight(root->left) + getHeight(root->right);
}
void showExpoLevels(struct TreeNode *node) {
   int treeSize = getHeight(node);
   // Create a queue
   struct TreeNode *queue[treeSize];
   // Push root node in a queue
   queue[0] = node;
   getExpLevels(node, queue, 0, 1);
}
int main() {
   TreeNode *root = newNode(25);
   root->left = newNode(16);
   root->right = newNode(64);
   root->left->left = newNode(5);
   root->left->right = newNode(15);
   root->right->left = newNode(20);
   root->right->right = newNode(10);
   root->right->left->left = newNode(10);
   root->right->right->right = newNode(100);
   executeSieve();
   showExpoLevels(root);
   return 0;
}